Published on: 05/07/2024

Leetcode #128 : Longest Consecutive Sequence

Intuition

It turns out that our initial brute force solution was on the right track, but missing a few optimizations necessary to reach O(n) time complexity.

Algorithm

This optimized algorithm contains only two changes from the brute force approach: the numbers are stored in a HashSet (Or Set, in Python) to allow O(1) lookups, and we only attempt to build sequences from numbers that are not already part of a longer sequence. This is accomplished by first ensuring that the number that would immediately precede the current number in a sequence is not present, as that number would necessarily be part of a longer sequence.

class Solution{
    public int longestConsecutive(int[] nums){
        Set<Integer> num_set = new HashSet<Integer>();
        for(int num: nums){
            num_set.add(num);
        }

        int longestStreak = 0;

        for(int num: num_set){
            if(!num_set.contains(num - 1)){
                int currentNum = num;
                int currentStreak = 1;

                while(num_set.contains(currentNum + 1)){
                    currentNum += 1;
                    currentStreak +=1;
                }
                longestStreak = (currentStreak > longestStreak) ? currentStreak : longestStreak;
            }
        }
        return longestStreak;
    }


}

Leetcode #167 : Two Sum II - Input Array Is Sorted

Algorithm

We can apply Two Sum’s soultions directly to get O(n^2) time, O(1) space using brute force and O(n) time, _O(n) space using hash table. However, both existing solutions do not make use of property that the input array is sorted. We can do better.

We use two indecies, initially pointing to the first and last element, respectively. Compare two sum of these two elements with target. If the sum is equal to target, we found the exacttly only solution. If it is less than target, we increase the smaller index by one. If it is greater than target, we decrease the larger index by one. Move the indices and repeat the ocmparison until the solution is found.

Let _[…, a, b, c, …, d, e, f, …] be the input array that is sorted in ascending order and let the elements b and e be the exactly only solution. Because we are moving the smaller index from left to right, and the larger index form right to left, at some point, one of the indices must react either b or e. Without loss of generality, suppose the snmaller index reaches b first. At this time, the sume of these two elements must be greate than target. Based on out algorithm, we will keep moving the larger index to the left until we reach the solution.

Implementation.

class Solution{
    public int[] twoSum(int[] numbers, int target){
        int low = 0;
        int high = numbers.length - 1;

        while(low < high){
            int sum = numbers[low] + numbers[high];

            if(sum == target)
                return new int[] {low + 1, high + 1};
            else if(sum > target){
                --high;
            }
            else{
                ++low;
            }

        }
        // In case there is no solution, return {-1, -1}
        return new int[] {-1, -1};
    }


}

Leetcode #238 : Product of Array Except Self

Algorithm

Initialize two empty arrays, L and R where for a given index i, L[i] would contain the product of all numbers to the left of i and R[i] would contain the product of all numbers to the right of i.

Implementation.

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

        // Init right side sum
        for(int i = nums.length - 2; i > 0; i--){
            products[i] = products[i + 1] * nums[i];
        }
        sol[0] = products[1];
        int lSum = 1;

        // Build solution array
        for(int i = 1; i < sol.length - 1; i++){
            lSum = lSum * nums[i - 1];
            sol[i] = lSum * products[i + 1];
        }

        // Fill in final element
        sol[sol.length - 1] = lSum * nums[nums.length - 2];
        
        return sol;
    }


}