subarray sum

Question:

Given an array in arbitrary order, find if there exists a contiguous subarray sum up to the target.

Example:

arr = [5, 1, 3, 7, 21]

target = 1
output: true

target = 4
output = true

target = 8
output = false

target = -10 (hint that the array may include negative number)
output = false


 Solution:

// brute-force  O(n^3)
boolean findTarget(int[] arr, int target) {
  for (int i = 0; i < arr.size(); i++) {
    for (int j = i + 1; j < arr.size(); j++) {
      int sum = 0;
      for (int k = i; i <= j; i++) {
        sum += arr[k];
        if (sum == target) {
          return true;
        }
      }
    }
  }
  return false;
}

// optimized brute-force O(n^2)
boolean findTarget(int[] arr, int target) {
  for (int i = 0; i < arr.size(); i++) {
    int sum = 0;
    for (int j = i; j < arr.size(); j++) {
      sum += arr[i];
      if (sum == target) {
       return true;
      }
    }
  }
  return false;
}

// hashset time O(n) space O(n)
boolean findTarget(int[] arr, int target) {
  HashSet<Integer> set = new Hashset();
  int sum = 0;
  for (int i = 0; i < arr.size(); i++) {
   if (set.has(sum - target)) {
      return true;
    }
    set.add(sum);
  }
  return false;
}

// sliding window (assume array only have non-negative numbers)
boolean findTarget(int[] arr, int target) {
  int left = 0;
  int right = 0;
  int sum = 0;
  while (left <= right && right < arr.size()) {
    sum += arr[right];
    right += 1;
   while (sum > target && left < right) {
      sum -= arr[left];
      left += 1;
    }
    if (sum == target) {
      return true;
    }
  }
  return false;
}

938. Range Sum of BST

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23


Note:

The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.


Solution:

Generally for a tree problem, we can think of either using a recursive traversal, or bfs.

We choose to use recursion here.

Knowing the property of BST and given a root node.
1. The exit condition is that when root is null, we return 0.
2. If root.val < L, we know all nodes in its left subtree are smaller than L. So we do not need to count that. We only consider its right subtree.
3. If root.val > R, we know all nodes in its right subtree are larger than R. So we do not need to count that. We only consider its left subtree.
4. If root.val is between L and R, we need to count this value. And we need to count both its left and right subtrees recursively.

The time complexity is O(n), assume n is the total number of nodes, since each node will be traversed only once.


Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0;
        if (root.val < L) return rangeSumBST(root.right, L, R);
        if (root.val > R) return rangeSumBST(root.left, L, R);
        return root.val 
            + rangeSumBST(root.right, L, R) 
            + rangeSumBST(root.left, L, R);
    }
}

939. Minimum Area Rectangle

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn't any rectangle, return 0.


Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2


Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.


Solution:

The brute-force way is to use four for loops to iterate all four points. For each four points, we can determine whether they can form a rectangular and maintain a minimum size.

If 4 points can form a rectangular, they have to be (x₁, y₁), (x₁, y₂), (x₂, y₁), and (x₂, y₂). We can see x₁ exists twice, x₂ exists twice, y₁ exists twice and y₂ exists twice. We can implement an isValid function with this logic.

The bruce-force approach takes O(n⁴) time, which is not good.

A better solution is we can go through all points in O(n) and maintain a HashMap. For each x, we maintain a Set in the map that contains all existing y corresponding to this x.

After building up the map, we can use two for loops to choose any two points in the input. For each two points (A and B), we first determine if they are diagonal. If they are diagonal, we know these two points have different x and different y.

Then we can use the map to check:
1.  there exists a point which has A's x and B's y
2.  there exists a point which has B's x and A's y
3.  check size

This takes O(1) time.

In this way, we can solve the problem in O(n²) time with an additional space for the map.


Code:

class Solution {
    public int minAreaRect(int[][] points) {
        int res = Integer.MAX_VALUE;
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int[] point : points) {
            if (!map.containsKey(point[0])) {
                map.put(point[0], new HashSet<>());
            }
            map.get(point[0]).add(point[1]);
        }
        for (int[] pointA : points) {
            for (int[] pointB : points) {
                if (pointA[0] == pointB[0] || pointA[1] == pointB[1]) {
                    continue;
                }
                if (!map.get(pointA[0]).contains(pointB[1]) 
                    || !map.get(pointB[0]).contains(pointA[1])) {
                    continue;
                }
                res = Math.min(res, 
                               Math.abs((pointB[0] - pointA[0]) 
                                        * (pointB[1] - pointA[1])
                                        )
                              );
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

941. Valid Mountain Array

Given an array A of integers, return true if and only if it is a valid mountain array.

Recall that A is a mountain array if and only if:

A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[B.length - 1]


Example 1:

Input: [2,1]
Output: false

Example 2:

Input: [3,5,5]
Output: false

Example 3:

Input: [0,3,2,1]
Output: true


Solution:

The idea is to:
1. check the array is increasing and find the peak
2. check the rest of array is decreasing

Since we check each element at most twice. The time complexity is O(n).


Code:

class Solution {
    public boolean validMountainArray(int[] A) {
        if (A == null || A.length < 3) {
            return false;
        }
        int peak = 0;
        while (peak + 1 < A.length) {
            if (A[peak + 1] <= A[peak]) {
                break;
            }
            peak++;
        }
        if (peak == 0 || peak == A.length - 1) {
            return false;
        }
        while (peak + 1 < A.length) {
            if (A[peak] <= A[peak + 1]) {
                return false;
            }
            peak++;
        }
        return true;
    }
}

942. DI String Match

Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

If S[i] == "I", then A[i] < A[i+1]
If S[i] == "D", then A[i] > A[i+1]


Example 1:

Input: "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: "III"
Output: [0,1,2,3]

Example 3:

Input: "DDI"
Output: [3,2,0,1]


Solution:

From the above examples, we can see if the first character is "I", we should choose the smallest number in the range, which is 0. And if the first character is "D", we need to choose the largest number in the range, which is N.

After each choice, we shrink the range.

From the second character, we apply the same logic.

Therefore, we can solve this problem in O(n) time.


Code:

class Solution {
    public int[] diStringMatch(String S) {
        int N = S.length();
        int increase = 0;
        int decrease = N;
        int[] res = new int[N + 1];
        for (int i = 0; i < N; i++) {
            char c = S.charAt(i);
            if (c == 'I') {
                res[i] = increase++;
            } else { // c == 'D'
                res[i] = decrease--;
            }
        }
        res[N] = increase;
        return res;
    }
}

437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution:

We can recursively check:

1. can we get a path sum to target from current node?
2. can we get a path sum to target from the child of this node?


Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    public int helper(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return (sum == root.val ? 1 : 0) + helper(root.left, sum - root.val) + helper(root.right, sum - root.val);
    }
}

443. String Compression

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.


Follow up:
Could you solve it using only O(1) extra space?


Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.


Note:
1. All characters have an ASCII value in [35, 126].
2. 1 <= len(chars) <= 1000.


Solution:

This problem is similar to count and say.

We iterate the input array and keep track of three pointers.

The first pointer points to the candidate character.

The second pointer points to the index that can be overwritten.

The third pointer points to the last character which is same to the candidate.

Therefore, we can use these three pointers to do in-place exchange.

The time complexity is O(n) and the space complexity is O(1).


Code:

class Solution {
    public int compress(char[] chars) {
        int candidate_idx = 0;
        int i = 0;
        for (int j = 0; j < chars.length; j++) {
            if (j == chars.length - 1 || chars[j] != chars[j + 1]) {
                chars[i++] = chars[candidate_idx];
                if (j > candidate_idx) {
                    for (char c : ("" + (j - candidate_idx + 1)).toCharArray()) {
                        chars[i++] = c;
                    }
                }
                candidate_idx = j + 1;
            }
        }
        return i;
    }
}

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: [1,2,3,1], k = 3
Output: true

Example 2:

Input: [1,0,1,1], k = 1
Output: true

Example 3:

Input: [1,2,1], k = 0
Output: false


Solution:

In this array if we can find index i and j such that nums[i] == nums[j] and j - i <= k, return true. If we cannot find such i and j, return false.

We can iterate through the array and maintain a HashMap to store the value we've already met, and it's index.

For any index i, if there exists the same value in the map, we check their distance. If the distance is <= k, return true. If not, we update this value in the map with a new index i.

When finish iterating the array, we do not find such pair, and return false.

The time complexity is O(n) and the space complexity is also O(n).


Code:

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

830. Positions of Large Groups

In a string S of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like S = "abbxxxxzyy" has the groups "a", "bb", "xxxx", "z" and "yy".

Call a group large if it has 3 or more characters.  We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.


Example 1:

Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting  3 and ending positions 6.

Example 2:

Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.

Example 3:

Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]


Note:
1 <= S.length <= 1000


Solution:

This problem is similar to count and say.

We use two pointers to iterate the string.

The left pointer always point to the start of the character.

The right pointer goes right until it finds a different character and then check the distance between the left pointer and right pointer - 1.

Both left and right pointers only go one direction. Thus the time complexity is O(n).


Code:

class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> result = new ArrayList<>();
        int left = 0;
        int right = 0;
        while (left < S.length()) {
            while (right < S.length() && S.charAt(left) == S.charAt(right)) {
                right++;
            }
            if (right - left >= 3) {
                result.add(Arrays.asList(new Integer[]{left, right - 1}));
            }
            left = right;
        }
        return result;
    }
}

836. Rectangle Overlap

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.

Two rectangles overlap if the area of their intersection is positive.  To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two (axis-aligned) rectangles, return whether they overlap.

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true


Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false


Notes:

Both rectangles rec1 and rec2 are lists of 4 integers.
All coordinates in rectangles will be between -10^9 and 10^9.


Solution:

If two rectangles do not have overlap, given the first rectangle, the second rectangle could be only in these four positions:

1. above the first rectangle (rec2[0] >= rec1[2])
2. below the first rectangle (rec2[2] <= rec1[0])
3. right to the first rectangle (rec2[1] >= rec1[3])
4. left to the first rectangle (rec2[3] <= rec1[1])

Code:

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        return !(rec2[3] <= rec1[1] ||
                 rec2[1] >= rec1[3] ||
                 rec2[2] <= rec1[0] ||
                 rec2[0] >= rec1[2]);
    }
}

744. Find Smallest Letter Greater Than Target

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.

Examples:

Input:

letters = ["c", "f", "j"]

target = "a"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "c"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "d"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "g"

Output: "j"

Input:

letters = ["c", "f", "j"]

target = "j"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "k"

Output: "c"

Note:

letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

Solution:

1. From Note we know the array is not empty so there must be a solution.

2. We check the last char in the array. If target is greater or equal than the last char, the answer is the first char in the array.

3. Use binary search to find the fist element that is greater than target in this array.

Time complexity is O(logn).

Code:

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        if (target >= letters[letters.length - 1]) {
            return letters[0];
        }
        int start = 0;
        int end = letters.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (letters[mid] > target) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if (letters[start] > target) {
            return letters[start];
        }
        return letters[end];
    }
}

654. Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array. 
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

Note:

1. The size of the given array will be in the range [1,1000].

Solution:

Given an index, we can find the maximum value of its left and the maximum value of its right.

We recursively build the left max as left child and right max as right child.

For each node, we need O(n) to go through the array and find the max value. And we have n nodes in total.

Therefore, the time complexity is O(n²), and the space complexity is O(n).


Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildTree(nums, 0, nums.length);
    }
    
    public TreeNode buildTree(int[] nums, int left, int right) {
        if (left == right) {
            return null;
        }
        int maxIndex = findMax(nums, left, right);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = buildTree(nums, left, maxIndex);
        root.right = buildTree(nums, maxIndex + 1, right);
        return root;
    }

    public int findMax(int[] nums, int left, int right) {
        int maxIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

657. Judge Route Circle

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place. 

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L(Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:

Input: "UD"
Output: true

Example 2:

Input: "LL"
Output: false

Solution:

If we can move back to the origin, numbers of "U" should be the same with numbers of "D", while numbers of "L" should be the same with numbers of "R".


Code:

public class Solution {
    public boolean judgeCircle(String moves) {
        int vertical = 0;
        int horizontal = 0;
        for (char c : moves.toCharArray()) {
            if (c == 'U') {
                vertical++;
            }
            if (c == 'D') {
                vertical--;
            }
            if (c == 'R') {
                horizontal++;
            }
            if (c == 'L') {
                horizontal--;
            }
        }
        return vertical == 0 && horizontal == 0;
    }
}

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution:

The idea is to keep two pointers.

One points to the current non-duplicate node.

The other points to the candidate node.

Keep advancing the second pointer to the next non-duplicate node.

Connect these two nodes. (In this way we skip the duplicated nodes)

The time complexity is O(n).


Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode curr = head;
        while (curr != null) {
            while (curr.next != null && curr.val == curr.next.val) {
                curr = curr.next;
            }
            if (pre.next == curr) {
                pre = pre.next;
            }
            else {
                pre.next = curr.next;
            }
            curr = curr.next;
        }
        return dummy.next;
    }
}

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution:

The idea is to iterate through the Linked List and check if the adjacent nodes have the same value.

If so, we point the next of the current node to the next of its next.


Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode curr = head;
        while (curr != null && curr.next != null ) {
            if (curr.val == curr.next.val) {
                curr.next = curr.next.next;
            }
            else {
                curr = curr.next;
            }
        }
        return head;
    }
}

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

Solution:

The inorder sequence of BST is sorted.

So firstly we use O(n) time to construct a sorted ArrayList.

After that, we can apply two pointers from the start and end of the ArrayList to search for a target sum.

The time complexity of the search is also (n).

Thus, the time complexity is O(n) and the space complexity is O(n).


Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int i = 0;
        int j = list.size() - 1;
        while (i < j) {
            int sum = list.get(i) + list.get(j);
            if (sum == k) {
                return true;
            }
            else if (sum < k) {
                i++;
            }
            else {
                j--;
            }
        }
        return false;
    }

    public List<Integer> inorder(TreeNode root, List<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}