TWO POINTERS MOCK

977. Squares of a Sorted Array

Easy

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            nums[i] = nums[i] * nums[i];
        }
        int[] ans = new int[nums.length];
        int index = nums.length - 1;
        int i = 0;
        int j = nums.length - 1;
        while(i <= j){
            if(nums[i] <= nums[j]){
                ans[index] = nums[j];
                j--;
            }else{
                ans[index] = nums[i];
                i++;
            }
            index--;
        }
        return ans;
    }
}

15. 3Sum

Medium

Topics

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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-2; i++){
            if(nums[i] + nums[i + 1] + nums[i + 2] > 0){
                break;
            }
            if(nums[i] + nums[nums.length - 1] + nums[nums.length -2] < 0){
                continue;
            }
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k){
                if(nums[i] + nums[j] + nums[k] > 0){
                    k--;
                }else if(nums[i] + nums[j] + nums[k] < 0){
                    j++;
                }else{
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);
                    j++;
                    k--;
                    while(j < k && nums[j] == nums[j -1]){
                        j++;
                    }
                    while(j < k && nums[k] == nums[k + 1]){
                        k--;
                    }
                }
            }
        }
        return ans;
    }
}

18. 4Sum

Solved

Medium

Topics

Companies

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

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for(int a = 0; a < n - 3; a++){
            if((long)nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target){
                break;
            }
            if((long)nums[a] + nums[n - 1] + nums[n - 2] + nums[n -3] < target){
                continue;
            }
            if(a > 0 && nums[a] == nums[a -1]){
                continue;
            }
            for(int b = a + 1; b < n -2; b++){
                if((long)nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target){
                    break;
                }
                if((long)nums[a] + nums[b] + nums[n - 1] + nums[n - 2] < target){
                    continue;
                }
                if(b > a + 1 && nums[b] == nums[b -1]){
                    continue;
                }
                int c = b + 1;
                int d = n - 1;
                while(c < d){
                    long sum = (long)nums[a] + nums[b] + nums[c] + nums[d];
                    if(sum < target){
                        c++;
                    }else if(sum > target){
                        d--;
                    }else{
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[a]);
                        list.add(nums[b]);
                        list.add(nums[c]);
                        list.add(nums[d]);
                        ans.add(list);
                        c++;
                        d--;
                        while(c < d && nums[c] == nums[c -1]){
                            c++;
                        }
                        while(c < d && nums[d] == nums[d + 1]){
                            d--;
                        }
                    }
                }
            }
        }
        return ans;
    }
}

11. Container With Most Water

Medium

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length -1;
        int max = 0;
        while(left < right){
            max = Math.max(max, Math.min(height[left], height[right]) * (right - left));
            if(height[left] <= height[right]){
                left++;
            }else{
                right--;
            }
        }
        return max;
    }
}

42. Trapping Rain Water

Hard

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n - 1;
        int leftMax = 0;
        int rightMax = 0;
        int ans = 0;
        while(left < right){
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if(height[left] <= height[right]){
                ans += leftMax - height[left];
                left++;
            }else{
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
}