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

• Calculate the area
• 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);
//     }
}

Counting Bits - (LeetCode) - ans[i] = ans[i >> 1] + (i & 1);

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];

        for(int i = 0; i <= n; i++){
            // The number of set bits in 'i' is calculated based on a previous result.
            //
            // i >> 1: This is a bitwise right shift, equivalent to integer division by 2 (i / 2).
            // It gives us the number 'i' with its last bit removed. The bit count for this
            // smaller number, ans[i >> 1], has already been computed.
            //
            // i & 1: This is a bitwise AND with 1, equivalent to the modulo operator (i % 2).
            // It gives us the value of the last bit of 'i'. It's 1 if 'i' is odd, 0 if 'i' is even.
            //
            // So, ans[i] = (bits in the first part of i) + (the last bit of i).
            ans[i] = ans[i >> 1] + (i & 1);
        }

        return ans;
    }
}

Bit Manipulation - Missing Number - xorNums ^= nums[i] ^ i;  

class Solution {
    public int missingNumber(int[] nums) {
        int xorNums = nums.length;

        for(int i=0; i < nums.length; i++){
            xorNums ^= nums[i] ^ i;   
        }
        return xorNums;
    }
    // public int missingNumber(int[] nums) {
    //     Arrays.sort(nums);
    //     for(int i=0; i < nums.length; i++){
    //         if(i!=nums[i]) return i;   
    //     }
    //     return nums.length;
    // }
}

• 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