About Algorithm

Tips

• Use Set/Hashet for unique values https://leetcode.com/problems/contains-duplicate/
• Use Math.max(int,int) to get the max number between a number and a calculation. https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
• A product invert the sign, the max becomes the min, and the min becomes the max: https://leetcode.com/problems/maximum-product-subarray/
• (a & b) << 1 - is to carry

Array

Kadane’s Algorithm - adapted on cumulated products

    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[nums.length];

        // Calculate left product
        int leftProduct = 1;
        for (int i = 0; i < length; i++) {
            answer[i] = leftProduct;
            leftProduct *= nums[i];
        }

        // Calculate right product
        int rightProduct = 1;
        for (int i = length - 1; i >= 0; i--) {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return answer;
    }

Two Pass - (LeetCode)- to calculate the left and right products

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[nums.length];

        int leftProduct = 1;
        for (int i = 0; i < length; i++) {
            answer[i] = leftProduct;
            leftProduct *= nums[i];
        }

        int rightProduct = 1;
        for (int i = length - 1; i >= 0; i--) {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return answer;
    }
}

Binary Search - (LeetCode - LeetCode) - At every iteration, it divide the space by 2 using left or right.

• Find the pivot
• Binary Search to left side, Binary Search to right side

    private int binarySearch(
        int[] nums,
        int leftBoundary,
        int rightBoundary,
        int target
    ) {
        int leftIndex = leftBoundary;
        int rightIndex = rightBoundary;

        while (leftIndex <= rightIndex) {
            int midIndex = (leftIndex + rightIndex) / 2;
            int midValue = nums[midIndex];

            if (midValue == target) {
                return midIndex;
            } else if (midValue > target) {
                rightIndex = midIndex - 1;
            } else {
                leftIndex = midIndex + 1;
            }
        }
        return -1;
    }

3 Sum - (LeetCode) - fix a value, use left and right pointers

• Sort the array first !
• Fix I as length-2
• skip duplicates for I
• Move left and right pointers to match 0
• if one is found, skip duplicates and continue to search for other match
• if left & right pointers are equal, continue with a new I

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> results = new HashSet<>();

        for(int i = 0; i < nums.length - 2; i++){
            // Skip duplicates for fixed element
            if (i > 0 && nums[i] == nums [i - 1]) continue;

            int pointerLeft = i + 1;
            int pointerRight = nums.length -1;

            while(pointerLeft < pointerRight){
                int sum = nums[pointerLeft] + nums[i] + nums[pointerRight];
                
                if(sum == 0){
                    // Got one !
                    results.add(Arrays.asList(nums[pointerLeft], nums[i], nums[pointerRight]));

                    // Skip duplicates for left and right pointers
                    while(pointerLeft < pointerRight && nums[pointerLeft] == nums[pointerLeft + 1]){ pointerLeft++; }
                    while(pointerRight > pointerLeft && nums[pointerRight] == nums[pointerRight - 1]){ pointerRight--; }

                    pointerLeft++;
                    pointerRight--;
                }else if (sum < 0){
                    // Sum is too small, move left pointer to try to increase the sum
                    pointerLeft++;
                }else{
                    // Sum is too small, move right pointer to try to increase the sum
                    pointerRight--;
                }
            }
        }
        return new ArrayList<>(results);
    }
}

Two-Pointer Approach - (LeetCode) - Calculate the area and move pointers

class Solution {

   public int maxArea(int[] height) {
       int maxArea = 0;
       int pointerLeft = 0;
       int pointerRight = height.length - 1;

       while(pointerLeft < pointerRight){
           // Keep the lowest height to calculate the area for those two pointers
           int minHeight = Math.min(height[pointerLeft], height[pointerRight]);
           int area = minHeight * (pointerRight - pointerLeft);

           maxArea = Math.max(area, maxArea); 

           if (height[pointerLeft] < height[pointerRight]) {
               pointerLeft++;
           } else {
               pointerRight--;
           }
       }
       return maxArea;
   }

}

Binary

Sum of Two Integers - (LeetCode) - int carry = (a & b) << 1;

• Store the carry
• Get the rest

Think about this story: 2 bags of coins are emptied on a table. The overlapping pieces are carried in B. The rest is stored in A

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1; 
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

Number of 1 bits - (LeetCode) - if ((n & mask) != 0)

• The equivalent of a pointer in an array is here a Mask, we move it using <<= 1 to the next bit
• And continue to 32 bits as it is mentioned in the exercise.
• & is a binary AND

class Solution {
    public int hammingWeight(int n) {
        int bits = 0;
        int mask = 1;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) {
                bits++;
            }
            mask <<= 1;
        }
        return bits;
    }
//     public int hammingWeight(int n) {
//         return Integer.bitCount(n);
//     }
}

• QuickSort (Java)
• Bit Manipulation
• Backtracking
• Graph Traversal
• Union-Find
• Dynamic Programming
• Greedy
• Sliding Window / Two Pointers
• BubbleSort (Java)
  • Swapping the adjacent numbers two by two by order

Graphs

• Dijkstra
• Topologic sorting

Cryptography & Compression

• Shannon-Fano
• Huffman
• Diffie-Hellman
• RSA

Prime Numbers

• ?

Most beautiful Equation

• P=NP (Les Équations de Yang Mills)
• Millenium problems (Clay Mathematics Institute)
• Few ideas