[LeetCode] 594. Longest Harmonious Subsequence

Problem : https://leetcode.com/problems/longest-harmonious-subsequence/description/

Since we only need the length of the subsequence, we don't need to preserve the original order of the numbers. We can sort the origin array in non-decreasing order and use sliding window to find the longest subsequence.

The left pointer points to the minmum value and the right pointer points to the maximum value.

Move left pointer to right, when the difference is larger than 1.

Move right pointer to right, when the difference is smaller or equal to 1.

Update the longest subsequence length when the difference is equal to 1.

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);

        int left = 0; 
        int result = 0;
        for (int right = 0; right < nums.length;) {
            long diff = nums[right] - nums[left];
            if (diff < 1L) {
                right++;
                continue;
            }
            if (diff == 1L) {
                result = Math.max(result, right - left + 1);
                right++;
                continue;
            }
            left += 1;
        }
        
        return result;
    }

[LeetCode] 1007. Minimum Domino Rotations For Equal Row

Problem : https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/description/

To reach the goal of this problem, we can:

Lock the first column and rotate the other columns to match the top value the first column.

Lock the first column and rotate the other columns to match the bottom value the first column.

Rotate and lock the first column, then rotate the other columns to match the top value of the first column.

Rotate and lock the first column, then rotate the other columns to match the bottom value of the first column.

The answer is minimum rotation count of the above 4 usecases.

class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int rotationCountForMatchingTop = helper(tops[0], tops, bottoms);
        int rotationCountForMatchingBottom = helper(bottoms[0], tops, bottoms);
        
        if (rotationCountForMatchingTop == -1 && rotationCountForMatchingBottom == -1)
          return -1;

        if (rotationCountForMatchingTop == -1)
          return rotationCountForMatchingBottom;

        if (rotationCountForMatchingBottom == -1)
          return rotationCountForMatchingTop;

        return Math.min(rotationCountForMatchingTop, rotationCountForMatchingBottom);
    }

    int helper(int target, int[] A, int[] B) {
      int rotateToTop = 0, rotateToBottom = 0;
      for (int i = 0; i < A.length; i++) {
        if (target != A[i] && target != B[i]) {
          // There is no way to rotate the current domino to match the target value.
          return -1;
        }

        if (target != A[i]) {
          rotateToTop += 1;
        }

        if (target != B[i]) {
          rotateToBottom += 1;
        }
      }

      return Math.min(rotateToTop, rotateToBottom);
    }
}

[LeetCode] 2140. Solving Questions With Brainpower

Problem: https://leetcode.com/problems/solving-questions-with-brainpower/description/

Similar to the House Robber problem. For each question, we need to consider these 2 cases:

The point we can get if we solve this problem and solve or skip the next eligible problem.

The point we can get if we skip this problem and solve or skip the next eligible problem.

Time Complexity : O ( N )

Space Complexity : O ( N )

class Solution {
    public long mostPoints(int[][] questions) {
        int N = questions.length;

        // maximum point when pick the 'i' question
        long[] pick = new long[N];
        // maximum point when skip the 'i' question
        long[] skip = new long[N];

        for (int i = N-1; i >= 0; i--) {
          // solve the 'i' question
          pick[i] = questions[i][0];

          int j = i + questions[i][1] + 1;
          if (j < N) {
            // add on the point of picking / skip next eligible question 
            pick[i] += Math.max(pick[j], skip[j]);
          }

          // skip the 'i' question
          if (i + 1 < N) {
            // add on the point of picking / skip the next question 
            skip[i] = Math.max(pick[i+1], skip[i+1]);
          }
        }

        return Math.max(pick[0], skip[0]);
    }
}

[LeetCode] 2825. Make String a Subsequence Using Cyclic Increments

Problem : https://leetcode.com/problems/make-string-a-subsequence-using-cyclic-increments/

There are 2 important rules:

We only need to increase cyclically the character of str1 to match with a character of str2.

We only need to check if str2 is one of subsequences of str1. So we can use 2 pointers to compare the charaters of str1 and str2. When str1[i] == str2[j], we can move the 2 pointers forward. Otherwise, we just move forward the pointer i.

class Solution {

    public boolean canMakeSubsequence(String str1, String str2) {
        int M = str1.length(), N = str2.length();             
        int i = 0, j = 0;
        
        while (i < M && j < N) {
            int a = str1.charAt(i) - 'a', b = str2.charAt(j) - 'a';
            
            if (a == b || (a + 1) % 26 == b) {
                i += 1;
                j += 1;
            } else {
                i += 1;
            }
        }
        
        // Check if all characters of str2 have been matched
        return j == N;
    }
}

50 days badge of 2023

[Leetcode] 989. Add to Array-Form of Integer

 Problem : https://leetcode.com/problems/add-to-array-form-of-integer/description/

Add digit on each position from back. 

Time complexity = O (max(len(num), log(k))

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        LinkedList<Integer> result = new LinkedList<>();
        int carry = 0;
        int i = num.length - 1;

        while (i >= 0 || k > 0 || carry != 0) {
            int a = k % 10;
            int b = i >= 0 ? num[i--] : 0;

            k /= 10;

            result.addFirst((a + b + carry) % 10);
            carry = (a + b + carry) / 10;
        }

        return result;
    }
}

[LeetCode] 1162. As Far from Land as Possible

 Problem : https://leetcode.com/problems/as-far-from-land-as-possible/description/

Start from all the land cells and use BFS approach to calculate Manhattan distance for each water cells.

Manhattan distance means on each step, we can move to the 4 conjunctive cells ( up, down, left, right ).

Because of memorization, each cell will only be visited once.

Time complexity : O ( M * N ), M = len(grid), N = len(grid[0])

class Solution {
    static final int[][] diffs = new int[][] { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

    public int maxDistance(int[][] grid) {
        int ROW = grid.length;
        int COLUMN = grid[0].length;

        int[][] memo = new int[ROW][COLUMN];
        Deque<int[]> queue = new LinkedList<>();

        for (int y = 0; y < ROW; y++) {
            for (int x = 0; x < COLUMN; x++) {
                if (grid[y][x] == 1)
                     queue.offerLast(new int[] {y, x});
            }
        }

        int result = -1;
        int step = 1;
        
        while (!queue.isEmpty()) {
            int n = queue.size();

            for (int i = 0; i < n; i++) {
                int[] cur = queue.pollFirst();
                int cy = cur[0], cx = cur[1];

                for (int[] d : diffs) {
                    int ny = cy + d[0], nx = cx + d[1];

                    if (0 <= ny && ny < ROW && 
                        0 <= nx && nx < COLUMN && 
                        grid[ny][nx] == 0 && 
                        (memo[ny][nx] == 0 || memo[ny][nx] > step)) {
                        memo[ny][nx] = step;
                        queue.offerLast(new int[] {ny, nx});
                    }
                }
            }

            if (!queue.isEmpty()) {
                result = Math.max(result, step);
            }
            
            step += 1;
        }


        return result;
    }
}

[LeetCode] 904. Fruit Into Baskets

 Problem : https://leetcode.com/problems/fruit-into-baskets/

Use sliding window approach to find the maximum contiguous section contains 2 unique numbers.

Time complexity = O ( N ), N = len(fruits).

Because for each number, it will either be added to the window or removed from the window once.

class Solution {
    public int totalFruit(int[] fruits) {
        int[] counter = new int[fruits.length];
        int uniqNum = 0;

        int result = 0;

        int left = 0;
        for (int right = 0; right < fruits.length; right++) {
            counter[fruits[right]] += 1;
            if (counter[fruits[right]] == 1) {
                uniqNum += 1;
            }

            while (left <= right && uniqNum > 2) {
                counter[fruits[left]] -= 1;
                if (counter[fruits[left]]  == 0) {
                    uniqNum -= 1;
                }
                left += 1;
            }

            result = Math.max(result, right - left + 1);
        }

        return result;
    }
}

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

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