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

100 days badge of 2024

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