[LeetCode] 1249. Minimum Remove to Make Valid Parentheses

 Problem : https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

Instead of using stack, this is more like a greedy algorithm.

Scan the input string 2 times.  

The 1st time scan, find the total number of valid left and right parentheses.

The 2nd time scan, greedily add the valid left and right parentheses. 

Please be noticed, we cannot add right-parenthesis if there is no corresponding left-parenthesis be added before.

class Solution {
    public String minRemoveToMakeValid(String s) {
        char[] buffer = s.toCharArray();
        
        // find total number valid parentheses 
        int unmatchedLeft = 0;
        int validLeft = 0;
        int validRight = 0;
        
        for (char c : buffer) {
            if (c == '(') {
                unmatchedLeft += 1;
            } else if (c == ')') {
                if (unmatchedLeft > 0) {
                    unmatchedLeft -= 1;
                    
                    validLeft += 1;
                    validRight += 1;
                }
            }
        }
    
        // greedily add valid parentheses
        StringBuilder sb = new StringBuilder();
        int left = 0;
        int right = 0;
        
        for (char c : buffer) {
            if (c == '(' && left >= validLeft) {
                continue;
            }
            
            // cannot add right-parenthesis 
            // if there is no corresponding left-parenthesis be added before
            if (c == ')' && ( right >= validRight || left == right)) {
                continue;
            }
            
            sb.append(c);
            
            if (c == '(') {
                left += 1;
            } else if (c == ')') {
                right += 1;
            }
        }
        
        return sb.toString();
    }
}

[LeetCode] 1288. Remove Covered Intervals

 Problem : https://leetcode.com/problems/remove-covered-intervals/

Steps:

- Sort intervals by its beginning point in ascending order. If beginning point are the same, sort by ending point in descending order.

- Iterate all intervals.  If one interval cannot extend current ending point to further position, then it is covered and can be removed.

Time complexity = O ( N * Log(N) ) + O ( N )

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        int result = intervals.length;
        
        int rightSoFar = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][1] <= rightSoFar) {
                result -= 1;
            } else {
                rightSoFar = intervals[i][1];
            }
        }
        
        return result;
    }
}

[LeetCode] 438. Find All Anagrams in a String

 Problem : https://leetcode.com/problems/find-all-anagrams-in-a-string/

Use sliding window approach. 

Time complexity =  O (M) + O (N). M = length of s. N = length of p.

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        Map<Character, Integer> counter = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            counter.put(p.charAt(i), counter.getOrDefault(p.charAt(i), 0) + 1);
        }
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            counter.put(s.charAt(right), counter.getOrDefault(s.charAt(right), 0) - 1);
            while(left <= right && counter.get(s.charAt(right)) < 0) {
                counter.put(s.charAt(left), counter.get(s.charAt(left)) + 1);
                left += 1;
            }

            if (right + 1 - left == p.length()) {
                result.add(left);
            }
        }

        return result;
    }
}

Updated on 02/05/2023. Updated for a simplier sliding window solution which uses one hashmap to record the enoutered needed letters.

[LeetCode] 941. Valid Mountain Array

 Problem : https://leetcode.com/problems/valid-mountain-array/

Simulate the validation process.

class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) return false;
        
        int i = 0;
        
        // is strictly increasing
        while (i + 1 < arr.length && arr[i] < arr[i+1]) {
            i += 1;
        }
        
        if (i == 0 || i + 1 == arr.length) return false;
      
        // is strictly decreasing
        while (i + 1 < arr.length && arr[i] > arr[i+1] ) {
            i += 1;
        }
        
        return i+1 == arr.length;
    }
}

[LeetCode] 2064. Minimized Maximum of Products Distributed to Any Store

 Problem : https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/

If X is valid answer, all numbers larger than X is still valid answer. If X is invalid answer, all numbers less than X is still invalid answer. We may use binary search to 'guess' the minimum valid answer.

class Solution {
    
    /**
     Use binary search to find the lower bound of the valid maximum number of products
     Time complexity = O ( N * Log(M) ).  
     N = number of product types. M = maximum value of the quantities
    */
    public int minimizedMaximum(int n, int[] quantities) {
        int right = Arrays.stream(quantities).max().getAsInt();
        int left = 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (isValid(n, quantities, mid)) {
                // 'mid' is a valid answer. any number larger than X is still valid answer.
                //  move the right pointer to left side.
                right = mid;
            } else {
                // 'mid' is a invalid answer. any number less than X is still invalid anwser.
                // move the left pointer to right side.
                left = mid + 1;
            }
        }
        
        return right;
    }
    
    /**
     'mx' is valid if all products can be distrbuted to 'n' stores.
    */
    boolean isValid(int n, int[] quantities, int mx) {
        int neededStore = 0;
        
        for (int i = 0; i < quantities.length; i++) {
            // accumulate the number of store needed for product type 'i'
            neededStore += quantities[i] / mx;
            neededStore += (quantities[i] % mx == 0) ? 0 : 1;
        }
       
        return neededStore <= n;
    }
}

[LeetCode] 253. Meeting Rooms II

 Problem : https://leetcode.com/problems/meeting-rooms-ii/

The minimum required meeting rooms equals to the maximum meeting happen in parallel.

- Solution 1. Use counter to count the meetings happen in parallel.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] < b[0] ? -1 : 1;
            }
            
            return a[1] < b[1] ? -1 : 1;
        });
        for (int i = 0; i < intervals.length; i++) {
            pq.offer(new int[]{intervals[i][0], 1});
            pq.offer(new int[]{intervals[i][1], -1});
        }
        
        int count = 0;
        int result = 0;
        
        while (!pq.isEmpty()) {
            count += pq.poll()[1];
            result = Math.max(result, count);
        }
        
        return result;   
    }
}

- Solution 2. Use priority queue to save the meeting end time. The size of priority queue equals to the number of meetings happen in parallel.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] < b[0] ? -1 : 1;
            }
            
            return a[1] < b[1] ? -1 : 1;
        });
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int result = 0;
        
        for (int i = 0; i < intervals.length; i++) {
            while (!pq.isEmpty() && pq.peek() <= intervals[i][0]) {
                // the last meeting has ended.
                // remove it from the queue
                pq.poll();
            }
            
            pq.offer(intervals[i][1]);
            result = Math.max(result, pq.size());
        }
        
        return result;
    }
}

[LeetCode] 1345. Jump Game IV

 Problem : https://leetcode.com/problems/jump-game-iv/

Covert the array to a graph. Then use BFS find the shortest path.

class Solution {
    public int minJumps(int[] arr) {
        int N = arr.length;
        boolean[] visited = new boolean[N];
        
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < N; i++) {
            List<Integer> tmp = graph.getOrDefault(arr[i], new ArrayList<Integer>());
            tmp.add(i);
            graph.put(arr[i], tmp);
        }
        
        int step = 0;
        visited[0] = true;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curPos = queue.poll();
                if (curPos == N-1) {
                    return step;
                }
                
                if (curPos - 1 >= 0 && !visited[curPos - 1]) {
                    visited[curPos - 1] = true;
                    queue.offer(curPos - 1);
                }
                
                if (curPos + 1 < N && !visited[curPos + 1]) {
                    visited[curPos + 1] = true;
                    queue.offer(curPos + 1);
                }
                
                for (int nextPos : graph.get(arr[curPos])) {
                    if (nextPos != curPos && !visited[nextPos]) {  
                        visited[nextPos] = true;
                        queue.offer(nextPos);
                    }
                }
                
                // important! 
                // clear the neighbore pos list to avoid redundant visiting.
                graph.get(arr[curPos]).clear(); 
            }
            
            step += 1;
        }
        
        return step;
    }
}

[LeetCode] 893. Groups of Special-Equivalent Strings

 Problem : https://leetcode.com/problems/groups-of-special-equivalent-strings/

Because one character on odd position can be unlimitedly swapped with character on another odd position, the order of characters on odd position does not matter. Same to characters on even position. Two words are special-equivalent when they have same set of characters on odd positions and same set of characters on even positions.

class Solution {
    public int numSpecialEquivGroups(String[] words) {
        Set<String> group = new HashSet<>();
        
        for (String w: words) {
            group.add(keyOf(w));
        }
        
        return group.size();
    }
    
    String keyOf(String word) {
        int[] countOdd = new int[26];
        int[] countEven = new int[26];
        
        for (int i = 0; i < word.length(); i++) {
            if ((i & 1) == 1) {
                // odd position
                countOdd[word.charAt(i) - 'a'] += 1;
            } else {
                // even position
                countEven[word.charAt(i) - 'a'] += 1;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(Arrays.toString(countOdd));
        sb.append("-");
        sb.append(Arrays.toString(countEven));
       
        return sb.toString();
    }
}

[LeetCode] 861. Score After Flipping Matrix

 Problem: https://leetcode.com/problems/score-after-flipping-matrix/

- To get the maximum possible number, we need to flip all grid[y][0] to '1'.

- Because we did flip to the first column on the first step, the value on the grid[y][x] = 1 if grid[y][x] == grid[y][0]. Flip the values on each column to get as much ones as possible.

Because every row represents a binary number,  grid[y][x] is worth 1 << (COLUMN - x -1) points.

class Solution {
    public int matrixScore(int[][] grid) {
        int ROW = grid.length;
        int COLUMN = grid[0].length;
        
        // To get the maximum value, we need to toggle all grid[i][0] to '1'
        // And every grid[i][0] worths 1 << (COLUMN - 1) points
        
        int result = (1 << (COLUMN - 1)) * ROW;
        
        for (int x = 1; x < COLUMN; x++) {
            
            // count of one on current column
            int countOfOne = 0;
            
            for (int y = 0; y < ROW; y++) {
                
                // because we flipped grid[y][0] to 1
                // grid[y][x] will be '1' if it equals to grid[y][0]
                if (grid[y][x] == grid[y][0]) {
                    countOfOne += 1;
                }
            }
                
            int countOfZero = ROW - countOfOne;

            if (countOfZero > countOfOne) {
                // this column has more zeros than ones
                // flip zero to one to get more ones
                countOfOne = countOfZero;
            }

            // every one on this column worths 1 << (COLUMN - x - 1) points
            result += (1 << (COLUMN - x - 1)) * countOfOne;
        }
        
        return result;
        
    }
}

[LeetCode] 452. Minimum Number of Arrows to Burst Balloons

 Problem : https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

Sort the balloons by coordination first. Then combine the sections as much as possible.

class Solution {
    public int findMinArrowShots(int[][] points) {
        // sort points by its x coordination
        Arrays.sort(points, (a, b) -> {
            // don't use a[0] - b[0]. it may cause int overflow.
            if (a[0] != b[0]) {
                return a[0] < b[0] ? -1 : 1;
            }
            
            return a[1] < b[1] ? -1 : 1;
        });
        
        // assume every balloon needs one arrow
        int result = points.length;
        
        // start with the first ballon
        int right = points[0][1];
        
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] <= right) {
                // ith ballon can be bursted with the last balloon
                result -= 1;
                // update the right 
                right = Math.min(right, points[i][1]);
            } else {
                // start a new right
                right = points[i][1];
            }
        }
        
        return result;
    }
}

[LeetCode] 1022. Sum of Root To Leaf Binary Numbers

 Problem : https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/

Use DFS to get the result.

Time complexity = O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        // dfs
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        
        stack1.push(root);
        stack2.push(0);
        
        int result = 0;
        
        while(!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            int tmp = stack2.pop();
            
            tmp = (tmp << 1) | node.val;
            if (node.left == null && node.right == null) {
                result += tmp;
            }
            
            if (node.right != null) {
                stack1.push(node.right);
                stack2.push(tmp);
            }
            
            if (node.left != null) {
                stack1.push(node.left);
                stack2.push(tmp);
            }
        }
        
        return result;
    }
}

[LeetCode] 1463. Cherry Pickup II

 Problem : https://leetcode.com/problems/cherry-pickup-ii/

The final result only depends on the track of robot 1 and robot 2. The order of robot movement won't affect the final result. But if we move the 2 robots separately, the optimal track of one robot depends on the other robot's track. We will need to record the whole track of one robot to get the optimal track of another robot.

If we move the 2 robots synchronously, the optimal result only depends on the new position of the 2 robots on the next row.

class Solution {
    int ROW;
    int COLUMN;
    
    int[][] grid;
    int[][][] memo;
    
    int[] diff = new int[] {-1, 0, 1};
    
    public int cherryPickup(int[][] grid) {
        this.ROW = grid.length;
        this.COLUMN = grid[0].length;
        this.grid = grid;
        this.memo = new int[ROW][COLUMN][COLUMN];
        
        return helper(0, 0, COLUMN-1);
    }
    
    int helper(int y, int x1, int x2) {
        if (y >= ROW || x1 < 0 || x1 >= COLUMN || x2 < 0 || x2 >= COLUMN) {
            return 0;
        }
        
        if (memo[y][x1][x2] != 0) {
            return memo[y][x1][x2];
        }
        
        int result = x1 != x2 ? grid[y][x1] + grid[y][x2] : grid[y][x1];
        
        int tmp = 0;
        
        for (int dx1 : diff) {
            for (int dx2: diff) {
                tmp = Math.max(tmp, helper(y+1, x1 + dx1, x2 + dx2));
            } 
        }
        
        memo[y][x1][x2] = result + tmp;
        return memo[y][x1][x2];
    }
}

[LeetCode] 1094. Car Pooling

 Problem : https://leetcode.com/problems/car-pooling/

This problem is similar to the meeting room problems.

Use priority queue to process the timestamp when the 'occupied' counter be updated.

When 2 trips start on the same timestamp, it's important to decrease the 'occupied' counter first before increasing the 'occupied' counter.

Time complexity = O ( N * Log N ), N = length of the trips.

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        
        for ( int i=0; i < trips.length; i++) {
            // increase counter when the trip starts
            pq.offer(new int[]{trips[i][1], trips[i][0]});
            // decrease counter when the trip ends
            pq.offer(new int[]{trips[i][2], -1*trips[i][0]});
        }
        
        int occupied = 0;
        
        while (!pq.isEmpty() && occupied <= capacity) {
            occupied += pq.poll()[1];
        }
        
        return occupied <= capacity;
    }
}