[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