[LeetCode] 909. Snakes and Ladders

Problem : https://leetcode.com/problems/snakes-and-ladders/description/

This problem can be solved with BFS algorithm.

Each square on the board might be visited by regular visit or by using a ladder.   So each square has 2 visited states. Start from the index 1 square and use BFS algorithm to find the least steps to reach to the N*N square.

class Solution {
    public int snakesAndLadders(int[][] board) {
        int N = board.length;

        // Every square may be visited by a regular movement or by using a ladder
        boolean[][] visited = new boolean[N*N+1][2];

        Deque<Integer> queue = new LinkedList<>();
        queue.offerLast(1);
        visited[1][0] = true;

        int result = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                int currentIndex = queue.pollFirst();

                // reach the destination 
                if (currentIndex == N*N) {
                    return result;
                }
                
                for (int j = 1; j <= 6 && currentIndex + j <= N * N; j++) {
                    int nextIndex = currentIndex + j;
                    int[] nextPos = indexToPos(nextIndex, N);

                    if (board[nextPos[0]][nextPos[1]] != -1) {
                        // if the square has ladder
                        int jumpIndex = board[nextPos[0]][nextPos[1]];
                        
                        // check if this square has been visited by using ladder
                        if (visited[jumpIndex][1]) {
                            continue;
                        }

                        visited[jumpIndex][1] = true;
                        queue.offerLast(jumpIndex);
                    } else {
                        // if this square has been visited by regular movement
                        if (visited[nextIndex][0]) {
                            continue;
                        }
                        visited[nextIndex][0] = true;
                        queue.offerLast(nextIndex);
                    }

                }
            }

            result += 1;
        }

        return -1;
    }

    int[] indexToPos(int i, int N) {
        // find the row index
        int y = (N - 1)  - (i-1) / N;

        // find the column index
        int x = (i-1) % N;

        // revert the column order on the row "y" if it is needed
        if (y % 2 == N % 2) {
            x = (N-1) - x;
        }

        return new int[] { y, x };
    }
}

100 days badge of 2022

[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();
    }
}