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

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