Array

3Sum

Link: https://leetcode.com/problems/3sum/

Code:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length && nums[i] <= 0; ++i) {
            if (i == 0 || nums[i-1] != nums[i]) {
                twoSumII(i, nums, res);
            }
        }
        return res;
    }
    
    void twoSumII(int i, int[] nums, List<List<Integer>> res) {
        int low = i + 1, high = nums.length - 1;
        while (low < high) {
            int sum = nums[i] + nums[low] + nums[high];
            if ( sum > 0) {
                --high;
            } else if (sum < 0) {
                ++low;
            } else {
                res.add(Arrays.asList(nums[i], nums[low++], nums[high--]));
                while (low < high && nums[low] == nums[low - 1]) {
                    ++low;
                } 
            }
        }
    }
}

• Time complexity: O(n^2);

• Sort the array first (Arrays.sort()) and then use two pointers to find the target.

• Note how to create a new list in Java;

• Note how to add a new element to a list in Java (res.add(...));

• Note how to use Arrays.asList() to create a list from an array;

• Difference of post-increment and pre-increment (++i and i++);

• Difference between array and list in Java (List<Integer> and int[])?

3Sum Closest

Link: https://leetcode.com/problems/3sum-closest/

Code:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int diff = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && diff != 0; i++) {
            int low = i + 1, high = nums.length - 1;
            while (low < high) {
                int sum = nums[i] + nums[low] + nums[high];
                if (Math.abs(target - sum) < Math.abs(diff)) {
                    diff = target - sum;
                }
                if (sum < target) {
                    ++low;
                } else {
                    --high;
                }
            }
        }
        return target - diff;
    }
}

• Time complexity: O(n^2);

• Two pointers;

• Integer.MAX_VALUE is the largest integer in Java;

• Math.abs() is the absolute value of a number;

Product of Array Except Self

Link: https://leetcode.com/problems/product-of-array-except-self/

Code:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        LP, RP = [0] * length, [0] * length
        LP[0] = 1
        for i in range(1, length):
            LP[i] = LP[i-1] * nums[i-1]
        RP[length-1] = 1
        for i in range(length-2, -1, -1):
            RP[i] = RP[i+1] * nums[i+1]
        results = [0] * length
        for i in range(length):
            results[i] = LP[i] * RP[i]
        return results

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] leftProduct = new int[n];
        int[] rightProduct = new int[n];
        int[] finalProduct = new int[n];
        
        leftProduct[0] = 1;
        rightProduct[n-1] = 1;
        for (int i = 1; i < n; i++) {
            leftProduct[i] = leftProduct[i-1] * nums[i-1];
        }
        for (int i = n-2; i >= 0; i--) {
            rightProduct[i] = rightProduct[i+1] * nums[i+1];
        }
        
        for (int i = 0; i < n; i++) {
            finalProduct[i] = leftProduct[i] * rightProduct[i];
        }
        
        return finalProduct;
    }
}

• Time complexity: O(n);

• Space complexity: O(n);

Kids With the Greatest Number of Candies

Link: https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/

Code:

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        maxCandy = max(candies)
        nKids = len(candies)
        results = [False] * nKids
        for i in range(nKids):
            if candies[i] + extraCandies >= maxCandy:
                results[i] = True
        return results

• Time complexity: O(n);

• Space complexity: O(n).

Increasing Triplet Subsequence

Link: https://leetcode.com/problems/increasing-triplet-subsequence/

Code:

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first_num = float("inf")
        second_num = float("inf")
        for n in nums:
            if n <= first_num:
                first_num = n
            elif n <= second_num:
                second_num = n
            else:
                return True
        return False

• Time complexity: O(n);

• Space complexity: O(1).