Two Pointers - TwoSums, 3Sum, BST Sum, 4Sum - All variations

820

This post will be about building intuition for NSums variations of problems.

Update: I will add more variations soon

1. Two Sum


You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Constraints

Array is not sorted
Only one valid answer exists
Array does not contain duplicate numbers

Approach

Use a hashmap to contain the frequency count. If complement exists in the map, we have found our target

public int[] twoSum(int[] nums, int target) {

       Map<Integer, Integer> pair = new HashMap<>();
	   
       for(int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if(pair.containsKey(target - num))
                return new int[]{i, pair.get(target - num)};
            pair.put(num, i);
       }
       return new int[]{};
        
    }

167. Two Sum II - Input Array Is Sorted

Constraints:

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.

Approach

We will use the sorted property of the array

public int[] twoSum(int[] numbers, int target) {

        int low = 0 , high = numbers.length - 1;

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

        return new int[]{-1, -1};
    }

T: O(n)
S: O(1)

170. Two Sum III - Data structure design

Approach

We can use first approach and keep a hash map for count frequency

Optimizations

Boundary checks
- We can check for min and max of the array. If target is greater than 2 * max or less than 2 * min, it means it cannot exist in the array
Mid Element
- We can check if array contains mid value and count of mid should be >= 2.

class TwoSum {

    List<Integer> nums = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;

    public TwoSum() {
        nums = new ArrayList<>();
        map = new HashMap<>();
    }

    public void add(int number) {
        nums.add(number);
        map.put(number, map.getOrDefault(number, 0) + 1);
        if(min > number)
            min = number;
        if(max < number)
            max = number;

    }

    public boolean find(int value) {

        //Optimizations
        if(value < 2 * min || value > 2 * max)
            return false;
        
        if(value % 2 == 0)
            if(map.containsKey(value/2) && map.get(value / 2 ) >= 2)
                return true;
        for(int n : nums) {
            int comp = value - n;
            if((comp != n && map.containsKey(comp)) || ( comp == n  && map.get(comp) > 1) )
                return true;
        }
        return false;

    }
}

653. Two Sum IV - Input is a BST

Approach

Use the same sorted property of the BST

step 1:
check for the complement in current BST

Step 2:
If the current root is not part of anser, Check for left side and right side of the node

Boolean dfs(TreeNode root, TreeNode curr, int k) {

        if( curr == null)
            return false;
        
        
        int complement = k - curr.val;
        
        return search(root, curr,  complement) || dfs(root,curr.left, k) || dfs(root,curr.right, k);
    }

    Boolean search(TreeNode node,TreeNode curr,  int k) {

        while(node != null) {

            if(node != curr && node.val == k)
                return true;
            if(node.val > k)
                node = node.left;
            else 
                node = node.right;
        }
        return false;
    }

Approach 2:

Create Inorder list from BST and apply 2Sum on sorted list

	void inorder(List<Integer> list, TreeNode root) {
        if(root == null)
            return;
        inorder(list, root.left);
        list.add(root.val);
        inorder(list, root.right);
    }
	
	public boolean findTarget(TreeNode root, int k) {

        //Since it is BST, inorder traversal gives ascending order
        
         List<Integer> list = new ArrayList<>();
         inorder(list, root);

         int left = 0, right = list.size() - 1;

         while(left < right) {
            int sum = list.get(left) + list.get(right);
            if(sum == k)
                return true;
            if(sum < k)
                left++;
            else
                right--;
         }
         return false;
         
		 }

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] 
such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Brute Force:

Approach 1:

We can sort the array, loop through it and apply 2Sum using two pointers
Constraint: In order to avoid duplicates, we need to skip the duplicate elements

Variation: 3Sum ( No duplicates using sort + Two Pointers)

Optimization: nums[i] <=0

public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums); //nlogn
        List<List<Integer>> res = new ArrayList<>();
        
		//Optimization: nums[i] <= 0, if nums[i] is +ve, then we cannot find a result
        for(int i = 0; i < nums.length && nums[i] <=0; i++) {
            if( i == 0 || nums[i - 1] != nums[i])
                twoSums(nums, i, res);
        }
        return res;
        
    }

    void twoSums(int[] nums, int i, List<List<Integer>> res) {
        int low = i + 1, hi = nums.length - 1;
        while(low < hi ) {
            int sum = nums[low] + nums[hi] + nums[i];
            if(sum < 0)
                low++;
            else if (sum > 0)
                hi--;
            else {
                res.add(Arrays.asList(nums[i], nums[low], nums[hi]));
                while(low < hi && nums[low] == nums[low +1] )
                    low++;
                while(low < hi && nums[hi] == nums[hi - 1])
                    hi--;
               low++;
               hi--;
            }
        }
    }

259. 3Sum Smaller

Variation:

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Variation: Once we find a value <= target, all the numbers between left and right would be <=target. So we need to include (right - left) in the final answer

	
	 public int threeSumSmaller(int[] nums, int target) {

        Arrays.sort(nums);
        int sum = 0;

        for(int i = 0; i < nums.length - 2; i++) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i]);
        }
        return sum;
        
    }
    private int twoSumSmaller(int[] nums, int startIndex, int target) {
        int sum = 0;
        int left = startIndex;
        int right = nums.length - 1;

        while(left < right) {
            if(nums[left] + nums[right] < target) {
				// Everything between  right and left would be part of answer
                sum += right - left;
                left++;
            }else
                right--;
        }
        return sum;
    }

16. 3Sum Closest

Variation:

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.

Closest => Absolute distance from target. Keep track of min distance in internal loop.

public int threeSumClosest(int[] nums, int target) {
        int closestSum = Integer.MAX_VALUE / 2;
        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 2 && closestSum != 0; i++) {

            int low = i + 1;
            int high = nums.length - 1;

            //Optimization
            int minSum = nums[i] + nums[i + 1] + nums[i + 2];
            if( minSum >= target + Math.abs(target - closestSum))
                return closestSum;

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

                
                if(Math.abs(target - sum) < Math.abs(closestSum - target)) {
                    closestSum = sum;
                }
                if(sum < target)
                    low++;
                else if(sum > target)
                    high--;
                else
                    return sum;
              }
        }

        return closestSum;

        
    }

18. 4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

In this problem, we have 4 variables - a, b, c, d.

So lets generalize the solution to n variables.

Template
 k - variables, targetSum
- Sort
- Boundary Checks
- Outer loop
	- Optimization
	-  k - 1 loops
		-  2Sum

 public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return kSum(nums, target, 0, 4);
        
    }
    public List<List<Integer>> kSum(int[] nums, long target, int start, int k) {
        List<List<Integer>> res = new ArrayList<>();

        if(start == nums.length)
            return res;

        //Optimization
        long avg_value = target / k;
        if(nums[start] > avg_value || avg_value > nums[nums.length - 1])
            return res;

        if(k == 2)
            return twoSum(nums, target, start);
        
        for(int i = start; i < nums.length; i++) {
            if( i == start || nums[i- 1] != nums[i])
                for(List<Integer> subset: kSum(nums, (long) target - nums[i], i + 1, k -1)) {
                    res.add(new ArrayList<>(Arrays.asList(nums[i])));
                    res.get(res.size() - 1).addAll(subset);
                }

        }
        return res;
        
    } 

    public List<List<Integer>> twoSum(int[] nums, long target, int start) {
        List<List<Integer>> res = new ArrayList<>();
        Set<Long> seen = new HashSet();

        int left = start, right = nums.length - 1;

        while(left < right) {
            long sum = (long) nums[left] + (long) nums[right];

            if(sum == target) {
                res.add(Arrays.asList(nums[left], nums[right]));
                while(left < right && nums[left] == nums[left + 1]) left++;
                while(left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;

            }else if(sum < target)
                left++;
            else
                right--;
        }
        return res;
    }

Comments (3)