DEV Community: Kaitian Xie

LeetCode in Java: 209

Kaitian Xie — Sun, 21 Apr 2019 00:01:18 +0000

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int sum = 0;
        int ans = Integer.MAX_VALUE;

        for (int l = 0, r = 0; r < nums.length; r++) {
            sum += nums[r];
            while (sum >= s) {
                ans = Math.min(ans, r - l + 1);
                sum -= nums[l++];
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

This problem is solved by using the two pointers l and r. In the for loop, we incrementally add the element at r to sum. Whenever the sum is greater or equal to s, we calculate the distance between the two pointers (r - l + 1) and if the distance is smaller than ans, we update ans with the distance. Then subtract the element at l from sum and increment l. At the end of the for loop, we should get the length of minimum subarray.

Time Complexity: O(n)

Extra Space: O(1)

LeetCode 111. Minimum Depth of Binary Tree

Kaitian Xie — Tue, 16 Apr 2019 01:53:14 +0000

public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> q = new LinkedList<>();
        TreeNode rightMost = root;
        q.add(root);
        int depth = 1;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left == null && node.right == null) {
                break;
            }
            if (node.left != null) {
                q.add(node.left);
            }
            if (node.right != null) {
                q.add(node.right);
            }
            if (node == rightMost) {
                depth++;
                rightMost = (node.right != null) ? node.right : node.left;
            }
        }

        return depth;
    }
}

We use BFS to solve this problem. We add nodes at the same level to a queue q. We iterate through each of the nodes. When we encounter a leaf node, we stop and return depth (the minimum depth). After iterating all the nodes at the same level, we still cannot find a leaf node, we increment depth by 1 then repeat the above process for the nodes at the next level. We can use DFS as well. However, BFS outperforms DFS on highly unbalanced trees since it terminates once it reaches the first leaf node.

Time Complexity: O(n)

Extra Space: O(1)

LeetCode 98. Validate Binary Search Tree

Kaitian Xie — Tue, 16 Apr 2019 01:38:54 +0000

Recursion

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValid(root, null, null);
    }

    private boolean isValid(TreeNode p, Integer low, Integer high) {
        if (p == null) {
            return true;
        }

        return (low == null || p.val > low) && (high == null || p.val < high) && isValid(p.left, low, p.val) && isValid(p.right, p.val, high);
    }
}

In a BST, a left child node is smaller than its parent and a right child node is always greater than its parent. The solution is based on this property. In the isValid function, we recursively check if a node has a value between low and high. There is an edge case where a node may have a value equal to Integer.MIN_VALUE or Integer.MAX_VALUE. So we use null to represent the infinity.

Time Complexity: O(n)

Extra Space: O(1)

In-Order Traversal

public class Solution {
    private TreeNode prev;

    public boolean isValidBST(TreeNode root) {
        prev = null;
        return isMonotonicIncreasing(root);
    }

    private boolean isMonotonicIncreasing(TreeNode p) {
        if (p == null) {
            return true;
        }

        if (isMonotonicIncreasing(p.left)) {
            if (prev != null && p.val <= prev.val) {
                return false;
            }
            prev = p;
            return isMonotonicIncreasing(p.right);
        }

        return false;
    }
}

If the tree is a valid BST, its elements should strictly follow an increasing order within an in-order traversal. We can use this property to solve the problem. To learn more about in-order traversal, please check out this link. We define prev to keep a track of the previous element in the in-order traversal. Whenever we detect that there exists a TreeNode p that is smaller than prev, we know the tree is not a valid BST.

Time Complexity: O(n)

Extra Space: O(1)

LeetCode 31. Next Permutation

Kaitian Xie — Fri, 12 Apr 2019 12:28:17 +0000

public class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
        int i = start;
        int j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

We iterate through nums from right to left to find the number nums[i] where the descending order occurs for the first time. Then we scan through the nums from right to i+1 to find a number that is greater nums[i] and swap the number with it. Finally, we reverse nums[i+1] ... nums[nums.length-1].

By doing so, we can guarantee that:

The next permutation is always greater or equal to the current permutation (we assume the numbers in the current permutation are not sorted in descending order).
There does not exist a permutation that is greater than the current permutation and smaller than the next permutation generated by the above code.
If the numbers in the current permutation are already sorted in descending order (i.e. greatest possible value), the next permutation has the smallest value.

Time Complexity: O(n)

Extra Space: O(1)

LeetCode 238. Product of Array Except Self

Kaitian Xie — Fri, 12 Apr 2019 05:41:02 +0000

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

        for (int i = 0, temp = 1; i < len; i++) {
            ans[i] = temp;
            temp *= nums[i];
        }
        for (int i = len - 1, temp = 1; i >= 0; i--) {
            ans[i] *= temp;
            temp *= nums[i];
        }

        return ans;
    }
}

After the first for loop, nums[i] is equal to the product of the numbers from 0 to i - 1. At each iteration of the second for loop, nums[i] is multiplied by the product of the numbers from i + 1 to len - 1. Therefore, after the two for loops, nums[i] = nums[0] * nums[1] * ... * nums[i-1] * ... * nums[i+1] * ... * nums[len-1].

Time Complexity: O(n)

Extra Space: O(1)

LeetCode 281. Move Zeros

Kaitian Xie — Thu, 11 Apr 2019 14:40:45 +0000

public void moveZeroes(int[] nums) {
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
            count++;
            continue;
        }
        if (count > 0) {
            swap(nums, i, i - count);
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

The essence of this approach is to swap a non-zero element with the left-most zero.

We iterate through the array nums and increment count by one when we encounter a zero, i.e. we calculate the distance between the left-most zero and a non-zero element. Once we meet a non-zero element, we swap it with the zero at i - count. At the end of the iteration, the zeros have been moved to the end and the relative positions of non-zero elements remain unchanged.

LeetCode 7. Reverse Integer

Kaitian Xie — Wed, 10 Apr 2019 01:33:19 +0000

public int reverse(int x) {
    int rev = 0;

    while (x != 0) {
        int pop = x % 10;
        x /= 10;

        if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) {
            return 0;
        }
        if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) {
            return 0;
        }

        rev = rev * 10 + pop;
    }

    return rev;
}

Reversing an integer is similar to reversing String. We get the last digit x % 10 and add it to rev. We repeat this process until x is 0. The two if statements are used to prevent integer overflows.

Time Complexity: O(log(x))

Extra Space: O(1)

A note on integer overflows

A integer occurs when the sum of rev * 10 + pop is greater/less than the maximum value (Integer.MAX_VALUE)/the minimum value(Integer.MIN_VALUE). So we need the check the values of rev and pop.

If rev > Integer.MAX_VALUE/10 or rev < Integer.MIN_VALUE/10, rev * 10 + pop will overflow.
If rev == Integer.MAX_VALUE / 10, pop must be less than or equal to 7 because 2^32 - 1 % 10 == 7.
If rev == Integer.MIN_VALUE / 10, pop must be greater than or equal to -8 because -2^32 % 10 == 8.

LeetCode 20. Valid Parentheses

Kaitian Xie — Tue, 09 Apr 2019 09:36:10 +0000

Stack (Optimized)

public boolean isValid(String s) {
    if (s == null || s.length() == 0) {
        return true;
    }

    int ptr = 0;
    char[] map = new char[s.length()];

    for (char ch : s.toCharArray()) {
        switch (ch) {
            case '(':
            case '{':
            case '[':
                map[ptr++] = ch;
                break;
            case ')':
                if (ptr == 0 || map[--ptr] != '(')
                    return false;
                break;
            case '}':
                if (ptr == 0 || map[--ptr] != '{')
                    return false;
                break;
            case ']':
                if (ptr == 0 || map[--ptr] != '[')
                    return false;
                break;
        }
    }

    return ptr == 0;
}

This problem can be solved by using a stack. The solution provided by LeetCode uses the Stack class. However, it can be simulated by an array. First, we create an empty array map that has the same size as the string s. Then we iterate through each character of s and when we encounter a left parenthesis, we store the parenthesis in map at the ptr index. Also, we increment ptr by one. (similar to push in Stack). If we encounter a right parentesis, we check if the right parenthesis has a corresponding left parenthesis stored at ptr -1 in map. If not, return false. Finally, we check if the ptr equals 0 (similar to an empty Stack).

Time Complexity: O(n)

Extra Space: O(n)

LeetCode in Ruby: 62. Unique Paths

Kaitian Xie — Tue, 19 Mar 2019 03:50:00 +0000

Backtracking

def unique_paths(m, n)
  backtrack(0, 0, m, n)
end

def backtrack(r, c, m, n)
  if r == m - 1 && c == n - 1
    return 1
  end
  if r >= m || c >= n
    return 0
  end
  backtrack(r + 1, c, m, n) + backtrack(r, c + 1, m, n)
end

This is a brute force approach to solve the problem. Don't submit this solution on LeetCode because it will exceed the time limit. It traverses all the possible paths by using a technique called backtracking.

Memorization (Top-Down)

def unique_paths(m, n)
  @cache = Array.new(m + 1) { Array.new(n + 1, -1) }
  backtrack(0, 0, m, n)
end

def backtrack(r, c, m, n)
  return 1 if r == m - 1 && c == n - 1
  return 0 if r >= m || c >= n

  @cache[r + 1][c] = backtrack(r + 1, c, m, n) if @cache[r + 1][c] == -1
  @cache[r][c + 1] = backtrack(r, c + 1, m, n) if @cache[r][c + 1] == -1
  @cache[r + 1][c] + @cache[r][c + 1]
end

Memorization (Bottom-Up)

def unique_paths(m, n)
  @cache = Array.new(m + 1) { Array.new(n + 1, 0) }
  @cache[m - 1][n] = 1
  (m - 1).downto(0).each do |r|
    (n - 1).downto(0).each do |c|
      @cache[r][c] = @cache[r + 1][c] + @cache[r][c + 1]
    end
  end
  @cache[0][0]
end

LeetCode in Ruby: 26. Remove Duplicates from Sorted Array

Kaitian Xie — Tue, 19 Mar 2019 03:37:22 +0000

def remove_duplicates(nums)
  nums.uniq!
  return nums.length
end

First, use uniq! to remove all the duplicates in nums. Then return its length.

Time complexity: O(n)

Extra memory: O(1)

LeetCode in Ruby: 56. Merge Intervals

Kaitian Xie — Tue, 19 Mar 2019 03:34:04 +0000

Sorting

def merge(intervals)
  merged = []
  intervals.sort_by! { |interval| interval.start }

  intervals.each do |interval|
    if merged.empty? || merged.last.end < interval.start
      merged << interval
    else
      merged.last.end = interval.end if interval.end > merged.last.end
    end
  end

  return merged
end

First of all, we sort the intervals list based on the start value of each interval in the list. Then we iterate through the list and append the current interval to the merged list if:

The merged list is empty, or
The last interval doesn’t overlap with the current interval, i.e. last.end < interval.start.

Otherwise we should update the end value of the last interval of the merged list. The updated end value should be greater than the previous one.

Time complexity: O(nlgn)

Extra memory: O(1)

LeetCode in Ruby: 771 Jewels and Stones

Kaitian Xie — Tue, 19 Mar 2019 03:19:41 +0000

1 Line

This approach is based on Ruby’s String#count method. It takes the string j as the set of characters to count in the string s. This is the fastest and the simplest solution.

Time complexity: O(j.length+ s.length)

Extra memory: O(1)

Hash

def num_jewels_in_stones(j, s)
  stones = Hash.new 0
  s.each_char do |char|
    stones[char] += 1
  end

  sum = 0
  j.each_char do |char|
    sum += stones[char]
  end

  return sum
end

First, we iterate through the string s and create a hash called stones that uses the characters in s as keys and their occurrence as values. Then we go through each character of j and sum up their occurrences.

Time complexity: O(j.length+ s.length)

Extra memory: O(s.length)