search – programmingpuzzles

Posted on May 27, 2019 by seeker

LeetCode – 98 : Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

    2
   / \
  1   3

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

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

[code lang="java"]
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        
    }
}
[code]

Idea – 1

val of every node must be within a range. For any bst , root's val must be in $(-\infty,\ \infty)$ . Root's left child’s value must be in $(-\infty,\ root.val)$ . Root's right child's val must be in $(root.val,\ \infty)$ . We apply this check recursively for each node. For an n-node bst, the time complexity is $O(n)$ and average recursion-stack depth is $O(\lg{n})$ .

[code lang="java"]
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    
    private boolean isValidBST(TreeNode x, Integer min, Integer max)
    {
        if(x == null)
        {
            return true;
        }
        
        boolean biggerThanMin = (min == null) || (min < x.val);
        boolean smallerThanMax = (max == null) || (x.val < max);
        
        return biggerThanMin
            && smallerThanMax 
            && isValidBST(x.left, min, x.val) 
            && isValidBST(x.right, x.val, max);
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Validate Binary Search Tree.Memory Usage: 37.8 MB, less than 94.08% of Java online submissions for Validate Binary Search Tree.

Idea – 2

Instead of putting pressure on thread's stack space (through recursion), we could use an explicit (heap-allocated) stack and do it iteratively. Asymptotic complexities remain unchanged.

[code lang="java"]
class Solution {
    
    class StackItem
    {
        TreeNode x;
        Integer min;
        Integer max;
        
        public StackItem(TreeNode x, Integer min, Integer max)
        {
            this.x = x;
            this.min = min;
            this.max = max;
        }
        
        public boolean biggerThanMin()
        { 
            return (this.min == null) || (x.val > this.min); 
        }
        
        public boolean smallerThanMax()
        {
            return (this.max == null) || (x.val < this.max);
        }
    }
    
    public boolean isValidBST(TreeNode root) {
        if(root == null)
        {
            return true;
        }
        
        Deque<StackItem> stack = new ArrayDeque<>();
        stack.addLast( new StackItem(root, null, null) );
        while(!stack.isEmpty())
        {
            StackItem top = stack.removeLast();
            if(!top.biggerThanMin() || !top.smallerThanMax())
            {
                return false;
            }
            
            if(top.x.left != null)
            {
                stack.addLast( new StackItem(top.x.left, top.min, top.x.val) );
            }
            
            if(top.x.right != null)
            {
                stack.addLast( new StackItem(top.x.right, top.x.val, top.max) );
            }
        }
        
        return true;
    }
}
[code]

Runtime: 2 ms, faster than 23.79% of Java online submissions for Validate Binary Search Tree.Memory Usage: 38.6 MB, less than 76.26% of Java online submissions for Validate Binary Search Tree.

Posted on May 13, 2019 by seeker

LeetCode – 79 : Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

[code lang="java"]
class Solution {
    public boolean exist(char[][] board, String word) {

    }
}
[code]

Idea – 1

We do dfs once from every cell of the board. A cell would stay ‘visited’ only for the fours sub-dfses from its four neighbors, otherwise we remove the cell from ‘visited’ list, this is to allow some other path to use this cell. Consider below, during dfs from cell x, we first visit its right neighbor cell y. All 4 neighbors of cell y fail to find a match, do we now keep cell y marked as ‘visited’?

No. Because there could be a legitimate path from x through x’s bottom neighbor and that path may require cell y like below:

Since the graph has $4\cdot n$ edges, we ignore edge count in the complexity. We are doing n dfs’es, time complexity is $O(n^2)$ and since we are doing a single dfs any one time space complexity is $O(n)$ .

[code lang="java"]
class Solution {
    public boolean exist(char[][] board, String word) {
        if(board==null)
        {
            return false;
        }
        
        if(board.length==0)
        {
            return word.isEmpty();
        }
        
        int m = board.length;
        int n = board[0].length;
        
        for(int row = 0; row < m; ++row)
        {
            for(int col = 0; col < n; ++col)
            {
                if(dfs(board, row, col, word, 0))
                {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean dfs(char[][] board, int row, int col, String word, int i)
    {
        if(i >= word.length())
        {
            return true;
        }
        
        int m = board.length;
        int n = board[0].length;
        
        if(row < 0 || row >= m || col < 0 || col >= n || board[row][col] == '*' || word.charAt(i) != board[row][col])
        {
            return false;
        }
        
        char old = board[row][col];
        board[row][col] = '*';
        
        boolean found = 
               dfs(board, row-1, col, word, i+1) 
            || dfs(board, row, col+1, word, i+1) 
            || dfs(board, row+1, col, word, i+1) 
            || dfs(board, row, col-1, word, i+1);
        
        board[row][col] = old;
        
        return found;
    }
}
[code]

Runtime: 4 ms, faster than 93.95% of Java online submissions for Word Search.Memory Usage: 37.4 MB, less than 96.83% of Java online submissions for Word Search.

Posted on May 3, 2019May 3, 2019 by seeker

LeetCode – 33 : Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 
Output: -1

[code lang="java"]
class Solution {
    public int search(int[] nums, int target) {
        
    }
}
[code]

Idea – 1

There are no duplicates. So, after rotation the single sorted array breaks into two sorted arrays separated by a break. We do modified binary search, deciding to go left or right but we need to consider cases when mid is to the left or to the right of the break. Time complexity is $O(\lg{n})$ and space is $O(1)$ .

[code lang="java"]
class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length-1;
        while(lo <= hi)
        {
            int mid = lo + (hi-lo)/2;
            
            if(target == nums[mid])
            {
                return mid;
            }
            else if(nums[mid] > nums[hi]) // mid is to the left of break
            {
                if(target >= nums[lo] && target < nums[mid]) // target is between lo and mid
                {
                    // go left
                    hi = mid-1;
                }
                else
                {
                    // go right
                    lo = mid+1;
                }
            }
            else // mid is to the right of break;
            {
                if(target > nums[mid] && target <= nums[hi]) // target is between mid and hi
                {
                    // go right
                    lo = mid+1;
                }
                else
                {
                    // go left
                    hi = mid-1;
                }
            }
        }
        
        return -1;
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array.
Memory Usage: 38.9 MB, less than 75.56% of Java online submissions for Search in Rotated Sorted Array.