Trapping Rain Water – leetcode

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

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Thought:
Take one element in the array as example, if we want to see how much water this position can trap, we will need to use Math.min(left highest boundary, right highest bundary) – current height. Thus, we need to calculate the left highest boundary for each position and the right highest boundary for each position.

Code:

   public int trap(int[] height) {
        if (height.length < 2)
            return 0;
        int len = height.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int max = height[0];
        for (int i = 0; i < len; i++) {
            max=Math.max (max, height[i]);
            left[i] = max;
        }
        max = height[len - 1];
        for (int i = len - 1; i >= 0; i--) {
            max=Math.max (max, height[i]);
            right[i] = max;
        }
        int re = 0;
        for (int i = 0; i < len ; i++) {
            re += Math.min (left[i], right[i]) - height[i];
        }
        return re;
    }

COMBINATION SUM II – leetcode

Question:
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Thought:
Similar as combination sum 1, difference is for each number we can only use once. before we do DFS call, we need to advance our index so in the subsequence dfs call, our current number will not be selected again.

Code:

   public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort (candidates);
        List <List <Integer>> result = new ArrayList <> ();
        combi (candidates, target, 0, new ArrayList <Integer> (), result);
        return result;
    }
    
    
    public void combi (int[] candidates, int target, int index, List <Integer> aList, List <List <Integer>> result) {
        if (target == 0) {
            result.add (aList);
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if(i!=index&&candidates[i]==candidates[i-1]) continue;
            List <Integer> tList = new ArrayList <> (aList);
            tList.add (candidates[i]);
            int newT = target - candidates[i];
            if (newT >= 0) {
                combi (candidates, newT, i+1, tList, result);
            } else {
                break;
            }
        }
    }

COMBINATION SUM – leetcode

Question:

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Thought:
Use DFS.
1. use index to keep track where we at in the array
2. use List to keep track current path.
3. use List<List> to save eligible result once find one
Things need attention:
1. Since for each number, we can use them more than once. Our index should not be incrementing in recursive calls.
2. To avoid dup results, in the loop, we need to check if our current value is the same as previous one. If so, skip this one.

Code:

  public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort (candidates);
        List <List <Integer>> result = new ArrayList <> ();
        combi2 (candidates, target, 0, new ArrayList <Integer> (), result);
        return result;
    }
    
    public void combi2 (int[] candidates, int target, int index, List <Integer> aList, List <List <Integer>> result) {
        if (target == 0) {
            result.add (aList);
            return;
        }
        for (int i = index; i < candidates.length; i++) {
           if(i!=index&&candidates[i]==candidates[i-1]) continue;
            List <Integer> tList = new ArrayList <> (aList);
            tList.add (candidates[i]);
            int newT = target - candidates[i];
            if (newT >= 0) {
                combi2 (candidates, newT, i, tList, result);
            } else {
                break;
            }
        }
    }

Count and Say — leetcode

Question:
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Thought:
There are 2 solutions.
The first one is start from n=1, assemble string based on previous string.
The second one is to using recursion, To assemble n=25, we use the string we get from n=24.
Both approach needs same logic for assemble string. We can use two pointers to count the appearance of the current char and then append to the string.

Code:

  public String countAndSay(int n) {
        if (n == 1)
            return "1";
        String re = countAndSay (n - 1);
        StringBuilder sb = new StringBuilder ();
        int count = 1;
        int i = 0;
        while (i < re.length ()) {
            int j = i + 1;
            char c = re.charAt (i);
            while (j<re.length ()&&re.charAt (j) == c) {
                j++;
                count++;
            }
            sb.append (count).append (c);
            count=1;//bug, remember to reset count
            i = j;
        }
        return sb.toString ();
    }

SUDOKU SOLVER –leetcode

Question:
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.’.
You may assume that there will be only one unique solution.

Thought:
Use DFS.
loop through the matrix, if we find empty cell. Start filling it from 1-9, validate our sudoku and continue filling the sudoku. if validation failed or we can not finish filling the rest sudoku by current value, then try next one.

Code:

   public void solveSudoku (char[][] board) {
        solveSoduku(board);
    }
    public boolean solveSoduku (char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int x = 1; x <= 9; x++) {
                        board[i][j] = (char) ('0' + x);
                        if (check (i, j, board)&&solveSoduku (board)) {
                            return true;
                        }
                        board[i][j] ='.';
                    }
                    return false;
                } 
            }
        }
        return true;
    }
     public boolean check (int x, int y, char[][] board) {
        // check row
        for (int i = 0; i < 9; i++) {
            if (i != y && board[x][i] == board[x][y]) {
                return false;
            }
        }
        for (int i = 0; i < 9; i++) {
            if (i != x && board[i][y] == board[x][y]) {
                return false;
            }
        }
        // check 9
        int rs = 0 + (x / 3) * 3;
        int cs = 0 + (y / 3) * 3;
        for (int i = rs; i < rs + 3; i++) {
            for (int j = cs; j < cs + 3; j++) {
                if ((i != x || j != y) && board[x][y] == board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

VALID SUDOKU – leetcode

Question:
Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Thought:
Straight forward. Check each element in the matrix, if it is not ‘.’, validate row, column and the 3*3 sub matrix the element is in.

Code:

 public boolean isValidSudoku (char[][] board) {
        int row = board.length;
        int col = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j]!='.'&&!check (i, j, board)) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean check (int x, int y, char[][] board) {
        int row = board.length;
        int col = board[0].length;
        // check row
        for (int i = 0; i < col; i++) {
            if (i != y && board[x][i] == board[x][y]) {
                return false;
            }
        }
        for (int i = 0; i < row; i++) {
            if (i != x && board[i][y] == board[x][y]) {
                return false;
            }
        }
        // check 9
        int rs = 0 + (x / 3) * 3;
        int cs = 0 + (y / 3) * 3;
        for (int i = rs; i < rs + 3; i++) {
            for (int j = cs; j < cs + 3; j++) {
                if ((i != x || j != y) && board[x][y] == board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

SEARCH INSERT POSITION – leetcode

Question:
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Thought:
Binary search. For each binary check, check boundary as well, that way we can find the position it is supposed to be inserted to.

Code:

 public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return 0;
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target) {
                if (mid - 1 < 0 || nums[mid - 1] < target)
                    return mid;
                else {
                    end = mid - 1;
                }
            } else {
                if (mid + 1 == nums.length || nums[mid + 1] > target) {
                    return mid + 1;
                }
                start = mid + 1;
            }
        }
        return -1;
    }

SEARCH FOR A RANGE – leetcode

Question:
Given a sorted array of integers, find the starting and ending position of a given target value.

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

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Thought:
1. use binary search to find a position in array that equals the target value.
2. use binary search to find left, right boundary.

Code:

public int[] searchRange(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int in = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target)
               { in = mid;
                break;}
            else if (nums[mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        if (in == -1) {
            int[] re2 = { -1, -1 };
            return re2;
        }
        int left = in;
        start = 0;
        end = in;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                left = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        int right = in;
        start = in;
        end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                right = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        int[] re = { left, right };
        return re;
    }

SEARCH IN ROTATED SORTED ARRAY – leetcode

Question:
Suppose a sorted array 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.

Thought:
Since it is rotated, we need to do a modification to standard binary search. After we get the mid position, the key is to find the half with right order sequence, if our target is in that range, then go to that half, otherwise go to the other half.

Things need attention: when check which half to go, don’t forget ‘==’ condition. See comment in code below.

Code:

 public int search(int[] nums, int target) {
        if (nums == null)
            return -1;
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[start] <= nums[mid]) {
                if (nums[start] <= target && nums[mid] > target) {// note, 
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (nums[mid] < target && nums[end] >= target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }

LONGEST VALID PARENTHESES – leetcode

Question:
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

Thought:
Use stack to install index. Iterate the string, if we found valid pair, we pop from stack. otherwise we push to the stack.
After one loop, we will have a stack which has all invalid char’s index. We iterate the stack and calculate the max length.

Things need attention: when calculate the length, don’t forget the last part and the fist part. Last part means (s.length()-1-stack.pop()+1) , the first part equals the first element in the stack.

Code:

     public int longestValidParentheses (String s) {
        if (s == null)
            return 0;
        Stack <Integer> stack = new Stack <> ();
        for (int i = 0; i < s.length (); i++) {
            char c = s.charAt (i);
            if (stack.isEmpty ()) {
                stack.push (i);
            } else {
                char c2 = s.charAt (stack.peek ());
                if (check (c2, c)) {
                    stack.pop ();
                } else {
                    stack.push (i);
                }
            }
        }
        if (stack.isEmpty ())
            return s.length ();
        int right = stack.pop();
        int max = s.length()-right-1;
        while (!stack.isEmpty ()) {
            int left = stack.pop ();
            max = Math.max (max, right - left -1);
            right = left;
        }
        max=Math.max(right,max);
        return max;
    }

    private boolean check (char c, char c2) {
        if (c == '(' && c2 == ')')
            return true;
        else
            return false;
    }