Forem: seanpgallivan

Solution: Redundant Connection

seanpgallivan — Fri, 25 Jun 2021 08:37:14 +0000

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #684 (Medium): Redundant Connection

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Examples:

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]

Output: [2,3]

Visual:

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]

Output: [1,4]

Visual:

Example 1:
Input:	edges = [[1,2],[1,3],[2,3]]
Output:	[2,3]
Visual:

Example 2:
Input:	edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output:	[1,4]
Visual:

Constraints:

n == edges.length

3 <= n <= 1000

edges[i].length == 2

1 <= ai < bi <= edges.length

ai != bi

There are no repeated edges.

The given graph is connected.

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

In this problem, the redundant edge will be the one that links together an already-linked graph. To determine whether already-seen segments of the graph have been connected, we can use a simple union-find (UF) implementation to keep track of the different segments.

With UF, we must define two functions: union and find. The find function will recursively trace a node's lineage back to its ultimate parent and update its value in the parent array (par), providing a shortcut for the next link.

The union function merges two segments by assigning the ultimate parent of one segment to another.

We can iterate through edges and find both vertices of the edge to see if they belong to the same segment. If so, we've located our redundant edge and can return it. If not, we should merge the two different segments with union.

Time Complexity: O(N) where N is the length of edges
Space Complexity: O(N) for par and the recursion stack

Javascript Code:

(Jump to: Problem Description || Solution Idea)



var findRedundantConnection = function(edges) {
    let par = Array.from({length: edges.length + 1}, (_,i) => i)
    const find = x => x === par[x] ? par[x] : par[x] = find(par[x])
    const union = (x,y) => par[find(y)] = find(x)
    for (let [a,b] of edges)
        if (find(a) === find(b)) return [a,b]
        else union(a,b)
};

Python Code:

(Jump to: Problem Description || Solution Idea)



class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        par = [i for i in range(len(edges) + 1)]
        def find(x: int) -> int:
            if x != par[x]: par[x] = find(par[x])
            return par[x]
        def union(x: int, y: int) -> None:
            par[find(y)] = find(x)
        for a,b in edges:
            if find(a) == find(b): return [a,b]
            else: union(a,b)

Java Code:

(Jump to: Problem Description || Solution Idea)



class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        par = new int[edges.length+1];
        for (int i = 0; i < par.length; i++)
            par[i] = i;
        for (int[] e : edges)
            if (find(e[0]) == find(e[1])) return e;
            else union(e[0],e[1]);
        return edges[0];
    }
    private int[] par;
    private int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    private void union(int x, int y) {
        par[find(y)] = find(x);
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)



class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        par.resize(edges.size()+1);
        for (int i = 0; i < par.size(); i++)
            par[i] = i;
        for (auto& e : edges)
            if (find(e[0]) == find(e[1])) return e;
            else uniun(e[0],e[1]);
        return edges[0];
    }
private:
    vector<int> par;
    int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    void uniun(int x, int y) {
        par[find(y)] = find(x);
    }
};

Solution: Out of Boundary Paths

seanpgallivan — Thu, 24 Jun 2021 09:08:36 +0000

Leetcode Problem #576 (Medium): Out of Boundary Paths

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent four cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 10^9 + 7.

Examples:

Example 1:

Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0

Output: 6

Visual:

Example 2:

Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1

Output: 12

Visual:

Example 1:
Input:	m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output:	6
Visual:

Example 2:
Input:	m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output:	12
Visual:

Constraints:

1 <= m, n <= 50

0 <= maxMove <= 50

0 <= startRow <= m

0 <= startColumn <= n

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

A brute force solution for this problem would be far too long since the number of possible paths is 4^maxMove. As is the case for most problems that contain overlapping paths, this problem can be simplified by combining these overlapping paths with the help of a dynamic programming (DP) approach.

In this instance, we can create a DP matrix in which each cell (dp[d][i][j]) represents the solution where d is the number of moves remaining and i and j are the coordinates of the starting location. We can then build this DP matrix up from d = 1 all the way up to d = maxMove.

To build up dp, we can start by filling in the starting values when d = 1, at which point each of the cells along the edges is a 1 and each corner is a 2. From there, we can iterate through the remaining values for d, and each cell will be the sum of the surrounding four cells from the previous move iteration (d-1), as those cells correspond to the possible previous positions before moving to the current cell.

Since we want to include any path that doesn't take up the full maxMove, the solution (ans) will then be the sum of the cells in dp that correspond to i = startRow and j = startColumn with all possible values for d.

To make things easier by preventing the need for out-of-bounds checks, we can add a buffer row/column on all four sides of the grid representations in dp filled with 0 values.

As we only ever use the previous iteration of d to build the current one, we can save space in this solution by compressing dp into only two 2D matrices (dpCurr, dpLast) instead of a 3D matrix of maxMove depth. We can do this by just swapping dpCurr and dpLast between each iteration and overwriting the old values in dpCurr as we iterate through. We can also then keep track of ans as we go.

We should also not forget to use the modulo operation on each cell value equation.

Time Complexity: O(N * M * L) where N and M are the dimensions of the grid and L is the maximum number of moves
Space Complexity: O(N * M) for the DP matrices

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var findPaths = function(m, n, maxMove, startRow, startColumn) {
    if (!maxMove) return 0
    let dpCurr = Array.from({length: m+2}, () => new Uint32Array(n+2)),
        dpLast = Array.from({length: m+2}, () => new Uint32Array(n+2))
    for (let i = 1; i <= m; i++)
        dpCurr[i][1]++, dpCurr[i][n]++
    for (let j = 1; j <= n; j++)
        dpCurr[1][j]++, dpCurr[m][j]++
    let ans = dpCurr[startRow+1][startColumn+1]
    for (let d = 1; d < maxMove; d++) {
        [dpCurr, dpLast] = [dpLast, dpCurr]
        for (let i = 1; i <= m; i++)
            for (let j = 1; j <= n; j++)
                dpCurr[i][j] = (dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007
        ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007
    }
    return ans
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        if maxMove == 0: return 0
        dpCurr = [[0] * (n+2) for _ in range(m+2)]
        dpLast = [[0] * (n+2) for _ in range(m+2)]
        for i in range(1, m+1):
            dpCurr[i][1] += 1
            dpCurr[i][n] += 1
        for j in range(1, n+1):
            dpCurr[1][j] += 1
            dpCurr[m][j] += 1
        ans = dpCurr[startRow+1][startColumn+1]
        for d in range(maxMove-1):
            dpCurr, dpLast = dpLast, dpCurr
            for i, j in product(range(1, m+1), range(1, n+1)):
                dpCurr[i][j] = (dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007
            ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007
        return ans

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove == 0) return 0;
        int[][] dpCurr = new int[m+2][n+2], dpLast = new int[m+2][n+2];
        for (int i = 1; i <= m; i++) {
            dpCurr[i][1]++;
            dpCurr[i][n]++;
        }
        for (int j = 1; j <= n; j++) {
            dpCurr[1][j]++;
            dpCurr[m][j]++;
        }
        int ans = dpCurr[startRow+1][startColumn+1];
        for (int d = 1; d < maxMove; d++) {
            int[][] temp = dpCurr;
            dpCurr = dpLast;
            dpLast = temp;
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    dpCurr[i][j] = (int)(((long)dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007L);
            ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007;
        }
        return ans;
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (!maxMove) return 0;
        vector<vector<int>> dpCurr(m+2, vector<int>(n+2)),
            dpLast(m+2, vector<int>(n+2));
        for (int i = 1; i <= m; i++)
            dpCurr[i][1]++, dpCurr[i][n]++;
        for (int j = 1; j <= n; j++)
            dpCurr[1][j]++, dpCurr[m][j]++;
        int ans = dpCurr[startRow+1][startColumn+1];
        for (int d = 1; d < maxMove; d++) {
            dpCurr.swap(dpLast);
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    dpCurr[i][j] = (int)(((long)dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007L);
            ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007;
        }
        return ans;
    }
};

Solution: Pascal's Triangle

seanpgallivan — Mon, 21 Jun 2021 08:05:05 +0000

Leetcode Problem #118 (Easy): Pascal's Triangle

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Examples:

Example 1:

Input: numRows = 5

Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1

Output: [[1]]

Example 1:
Input:	numRows = 5
Output:	[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:
Input:	numRows = 1
Output:	[[1]]

Constraints:

1 <= numRows <= 30

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

For this problem, we can do pretty much just as the instructions tell us. We'll iterate through the building of Pascal's triangle (ans), row by row. When we create each new row, we should initially fill it with 1s so that we don't have to worry about the logic of filling the edge cells that only have one number above.

Then we can start on j = 1 for each row and repeat the process of summing up the value of the current cell until we reach the midpoint (mid). Since the triangle is symmetrical, we can actually fill both halves of the row at once, while we work inward.

Once we reach the end of the last row, we can return ans.

Time Complexity: O(N) where N is the numRowsth triangular number
Space Complexity: O(1)

Javascript Code:

(Jump to: Problem Description || Solution Idea)



var generate = function(numRows) {
    let ans = new Array(numRows)
    for (let i = 0; i < numRows; i++) {
        let row = new Uint32Array(i+1).fill(1),
            mid = i >> 1
        for (let j = 1; j <= mid; j++) {
            let val = ans[i-1][j-1] + ans[i-1][j]
            row[j] = val, row[row.length-j-1] = val
        }
        ans[i] = row
    }
    return ans
};

Python Code:

(Jump to: Problem Description || Solution Idea)



class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [None] * numRows
        for i in range(numRows):
            row, mid = [1] * (i + 1), (i >> 1) + 1
            for j in range(1, mid):
                val = ans[i-1][j-1] + ans[i-1][j]
                row[j], row[len(row)-j-1] = val, val
            ans[i] = row
        return ans

Java Code:

(Jump to: Problem Description || Solution Idea)



class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>(numRows);
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>(i+1);
            while (row.size() <= i) row.add(1);
            int mid = i >> 1;
            for (int j = 1; j <= mid; j++) {
                int val = ans.get(i-1).get(j-1) + ans.get(i-1).get(j);
                row.set(j, val);
                row.set(row.size()-j-1, val);
            }
            ans.add(row);
        }
        return ans;
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)



class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows);
        for (int i = 0; i < numRows; i++) {
            vector<int> row(i+1, 1);
            int mid = i >> 1;
            for (int j = 1; j <= mid; j++) {
                int val = ans[i-1][j-1] + ans[i-1][j];
                row[j] = val;
                row[row.size()-j-1] = val;
            }
            ans[i] = row;
        }
        return ans;
    }
};

Solution: Swim in Rising Water

seanpgallivan — Sun, 20 Jun 2021 08:55:41 +0000

Leetcode Problem #778 (Hard): Swim in Rising Water

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Examples:

Example 1:

Input: [[0,2],[1,3]]

Output: 3

Explanation: At time 0, you are in grid location (0, 0).

You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.

When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]

Output: 16

Explanation: We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

The final route is marked in bold.

Visual:

Example 1:
Input:	[[0,2],[1,3]]
Output:	3
Explanation:	At time 0, you are in grid location (0, 0). You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0. You cannot reach point (1, 1) until time 3. When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:
Input:	[[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output:	16
Explanation:	We need to wait until time 16 so that (0, 0) and (4, 4) are connected. The final route is marked in bold.
Visual:

Constraints:

2 <= N <= 50

grid[i][j] is a permutation of [0, ..., N*N - 1].

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

When a problem asks us to find the best path when there is something quantifiable making certain paths worse than others, one natural option would be a Dijkstra's algorithm approach. Dijkstra's algorithm uses a breadth first search (BFS) approach to a graph traversal, but it takes into account the weight/distance/difficulty of the different edges.

In this case, the weight will be the time required to move to a particular cell. To use Dijkstra's, we'll need to use a min priority queue (or min heap) data structure to store the possible moves at any point. These moves will be prioritized by how early they can be achieved (represented by the value in grid[i][j]).

Starting at (0,0), we can iterate through the surrounding squares and enter them into our priority queue (pq). After we've entered possible cell move into pq, we should mark it as seen so that we don't enter the same cell into pq more than once.

(Note: The relative values for the grid coordinates and cell values are low enough that we can optionally store all three in one integer using bit manipulation to lower the memory footprint of the priority queue and make it a bit more responsive.)

We would normally create a seen matrix of N * N dimensions to keep track of this, but we can also use an in-place approach to keep this information in grid. To do this, we can just bump the cell value of the target cell above an arbitrarily high value. The maximum cell value will be N * N - 1, and since N caps out at 50, we can use any value of 2500 or more for our seen marker.

After we store the new possible moves in pq, we then move to the next cell indicated by pq, remembering to keep track of the largest cell value (priority) seen so far (ans). We should repeat this process until we reach the end cell, and then we can return ans.

Time Complexity: O(N^2 * log N) where N is the length of grid, for inserting/extracting up to N^2 entries into the priority queue
Space Complexity: O(N^2) for the priority queue / heap

Implementation:

Javascript's MinPriorityQueue() npm is less performant than a custom heap implementation, but it is decidedly easier to use. Both are included below.

C++ defaults to a max priority queue, so we can just flip the signs on each of the insertions and extractions to convert to a min priority queue.

Javascript Code:

(Jump to: Problem Description || Solution Idea)

w/ MinPriorityQueue():

const moves = [[1,0],[0,1],[-1,0],[0,-1]]

var swimInWater = function(grid) {
    let pq = new MinPriorityQueue(),
        N = grid.length - 1, ans = grid[0][0], i = 0, j = 0
    while (i < N || j < N) {
        for (let [a,b] of moves) {
            let ia = i + a, jb = j + b
            if (ia < 0 || ia > N || jb < 0 || jb > N || grid[ia][jb] > 2500) continue
            pq.enqueue((grid[ia][jb] << 12) + (ia << 6) + jb)
            grid[ia][jb] = 3000
        }
        let next = pq.dequeue().element
        ans = Math.max(ans, next >> 12)
        i = (next >> 6) & ((1 << 6) - 1)
        j = next & ((1 << 6) - 1)
    }
    return ans
};

w/ Custom Min-Heap:

const moves = [[1,0],[0,1],[-1,0],[0,-1]]

var swimInWater = function(grid) {
    let N = grid.length - 1, ans = grid[0][0], i = 0, j = 0, prio = 0

    // custom Min-Heap implementation
    let heap = [,]
    const hpush = val => {
        let i = heap.length, par = i >> 1, temp
        heap.push(val)
        while (heap[par] > heap[i]) {
            temp = heap[par], heap[par] = heap[i], heap[i] = temp
            i = par, par = i >> 1
        }
    }
    const hpop = () => {
        if (heap.length === 1) return null
        let top = heap[1], left, right, temp,
            i = 1, child = heap[3] < heap[2] ? 3 : 2
        if (heap.length > 2) heap[1] = heap.pop()
        else heap.pop()
        while (heap[i] > heap[child]) {
            temp = heap[child], heap[child] = heap[i], heap[i] = temp
            i = child, left = i << 1, right = left + 1
            child = heap[right] < heap[left] ? right : left
        }
        return top
    }

    while (i < N || j < N) {
        for (let [a,b] of moves) {
            let ia = i + a, jb = j + b
            if (ia < 0 || ia > N || jb < 0 || jb > N || grid[ia][jb] > 2500) continue
            hpush((grid[ia][jb] << 12) + (ia << 6) + jb)
            grid[ia][jb] = 3000
        }
        let next = hpop()
        ans = Math.max(ans, next >> 12)
        i = (next >> 6) & ((1 << 6) - 1)
        j = next & ((1 << 6) - 1)
    }
    return ans
};

Python Code:

(Jump to: Problem Description || Solution Idea)

moves = [[1,0],[0,1],[-1,0],[0,-1]]

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        N, i, j, pq, ans = len(grid) - 1, 0, 0, [], grid[0][0]
        while i < N or j < N:
            for a,b in moves:
                ia, jb = i + a, j + b
                if ia < 0 or ia > N or jb < 0 or jb > N or grid[ia][jb] > 2500: continue
                heappush(pq, (grid[ia][jb] << 12) + (ia << 6) + jb)
                grid[ia][jb] = 3000
            nxt = heappop(pq)
            ans = max(ans, nxt >> 12)
            i = (nxt >> 6) & ((1 << 6) - 1)
            j = nxt & ((1 << 6) - 1)
        return ans

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int swimInWater(int[][] grid) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int N = grid.length - 1, ans = grid[0][0], i = 0, j = 0;
        while (i < N || j < N) {
            for (int[] m : moves) {
                int ia = i + m[0], jb = j + m[1];
                if (ia < 0 || ia > N || jb < 0 || jb > N || grid[ia][jb] > 2500) continue;
                pq.add((grid[ia][jb] << 12) + (ia << 6) + jb);
                grid[ia][jb] = 3000;
            }
            int next = pq.poll();
            ans = Math.max(ans, next >> 12);
            i = (next >> 6) & ((1 << 6) - 1);
            j = next & ((1 << 6) - 1);
        }
        return ans;
    }
    private int[][] moves = {{1,0},{0,1},{-1,0},{0,-1}};
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        priority_queue<int> pq;
        int N = grid.size() - 1, ans = grid[0][0], i = 0, j = 0;
        while (i < N || j < N) {
            for (auto& m : moves) {
                int ia = i + m[0], jb = j + m[1];
                if (ia < 0 || ia > N || jb < 0 || jb > N || grid[ia][jb] > 2500) continue;
                pq.push(-(grid[ia][jb] << 12) - (ia << 6) - jb);
                grid[ia][jb] = 3000;
            }
            int next = -pq.top();
            pq.pop();
            ans = max(ans, next >> 12);
            i = (next >> 6) & ((1 << 6) - 1);
            j = next & ((1 << 6) - 1);
        }
        return ans;
    }
private:
    int moves[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
};

Solution: Number of Subarrays with Bounded Maximum

seanpgallivan — Thu, 17 Jun 2021 09:20:40 +0000

Leetcode Problem #795 (Medium): Number of Subarrays with Bounded Maximum

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

We are given an array nums of positive integers, and two positive integers left and right (left <= right).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least left and at most right.

Examples:

Example 1:

Input: nums = [2, 1, 4, 3]
left = 2
right = 3

Output: 3

Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Example 1:
Input:	nums = [2, 1, 4, 3] left = 2 right = 3
Output:	3
Explanation:	There are three subarrays that meet the requirements: [2], [2, 1], [3].

Constraints:

left, right, and nums[i] will be an integer in the range [0, 10^9].

The length of nums will be in the range of [1, 50000].

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The key to this problem is realizing that we're dealing with overlapping triangular number issues. Importantly, the total number of possible subarrays that are contained within any larger subarray is the Nth triangular number, where N is the length of that larger subarray.

So the nums array starts with the (nums.length)th triangular number total subarrays. We want to exclude any subarray that includes a number larger than right, however. The easiest way to do this is to consider numbers larger than right to be dividers, splitting nums into many subarrays. We can add the triangular number for each of these resulting subarrays together to be the total number of subarrays that exclude numbers higher than right.

To do this, we can iterate through nums and keep track of how many contiguous numbers are less than right (mid) and each point that mid increments, we can add mid to ans, representing the increase to the next triangular number. The value for mid will then reset whenever we see a number higher than right.

But this only does half of the problem, because we still have to also exclude any subarray that does not have any number at least left high. To do this, we can use a similar method as for mid. We can keep track of how many contiguous numbers are lower than left (low) and decrease ans by that amount every time it increments, representing the next triangular number. Similar to mid, low will reset whenever we see a number at least left high.

Once we're done iterating, we can return ans.

Visual example:

Time Complexity: O(N) where N is the length of nums
Space Complexity: O(1)

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var numSubarrayBoundedMax = function(nums, left, right) {
    let ans = 0, low = 0, mid = 0
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i]
        if (num > right) mid = 0
        else ans += ++mid
        if (num >= left) low = 0
        else ans -= ++low
    }
    return ans
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        ans, low, mid = 0, 0, 0
        for num in nums:
            if num > right: mid = 0
            else:
                mid += 1
                ans += mid
            if num >= left: low = 0
            else:
                low += 1
                ans -= low
        return ans

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int ans = 0, low = 0, mid = 0;
        for (int num : nums) {
            if (num > right) mid = 0;
            else ans += ++mid;
            if (num >= left) low = 0;
            else ans -= ++low;
        }
        return ans;
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int ans = 0, low = 0, mid = 0;
        for (auto num : nums) {
            if (num > right) mid = 0;
            else ans += ++mid;
            if (num >= left) low = 0;
            else ans -= ++low;
        }
        return ans;
    }
};

Solution: Generate Parentheses

seanpgallivan — Wed, 16 Jun 2021 08:42:44 +0000

Leetcode Problem #22 (Medium): Generate Parentheses

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Examples:

Example 1:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1

Output: ["()"]

Example 1:
Input:	n = 3
Output:	["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input:	n = 1
Output:	["()"]

Constraints:

1 <= n <= 8

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

We can make short work of this problem with a basic branching recursive function (dfs). Our recursive function will iterate through the index positions (pos) of a possible result. At each pos, we can add an open parenthesis if there's more remaining space than unclosed parentheses (open) and we can add a closed parenthesis if there are any unclosed parentheses. Once we reach the end of the result, we can add it to our answer array (ans).

To make things easier, we can use bit manipulation to pass the sequence of parentheses (seq) for our potential result as an integer to each new recursion level. Then we just have to translate seq to a parentheses string before adding it to ans.

Once we're all done, we can just return ans.

Time Complexity: O((2 * N)!/(N! * N!) reflecting the 2N choose N possible arrangements of parentheses
Space Complexity: O(N) for the recursion stack and res

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var generateParenthesis = function(N) {
    let ans = [], m = 2 * N

    const dfs = (pos, open, seq) => {
        if (pos === m) {
            let res = new Array(m)
            for (let i = 0; i < m; i++)
                res[i] = seq & 1 << i ? "(" : ")"
            ans.push(res.join(""))
            return
        }
        if (open) dfs(pos+1, open-1, seq)
        if (m - pos > open) dfs(pos+1, open+1, seq | 1 << pos)
    }

    dfs(0, 0, 0)
    return ans
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def generateParenthesis(self, N: int) -> List[str]:
        ans, m = [], 2 * N

        def dfs(pos: int, opn: int, seq: int) -> None:
            if pos == m:
                res = [0] * m
                for i in range(m):
                    res[i] = "(" if seq & 1 << i else ")"
                ans.append("".join(res))
                return
            if opn: dfs(pos+1, opn-1, seq)
            if m - pos > opn: dfs(pos+1, opn+1, seq | 1 << pos)

        dfs(0, 0, 0)
        return ans

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public List<String> generateParenthesis(int N) {
        ans = new ArrayList<>();
        m = 2 * N;
        dfs(0, 0, 0);
        return ans;
    }

    private List<String> ans;
    private int m;

    private void dfs(int pos, int open, int seq) {
        if (pos == m) {
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < m; i++)
                res.append((seq & 1 << i) > 0 ? "(" : ")");
            ans.add(res.toString());
            return;
        }
        if (open > 0) dfs(pos+1, open-1, seq);
        if (m - pos > open) dfs(pos+1, open+1, seq | 1 << pos);
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<string> generateParenthesis(int N) {
        m = 2 * N;
        dfs(0, 0, 0);
        return ans;
    }

private:
    vector<string> ans;
    int m;

    void dfs(int pos, int open, int seq) {
        if (pos == m) {
            string res = "";
            for (int i = 0; i < m; i++)
                res += seq & 1 << i ? "(" : ")";
            ans.push_back(res);
            return;
        }
        if (open) dfs(pos+1, open-1, seq);
        if (m - pos > open) dfs(pos+1, open+1, seq | 1 << pos);
    }
};

Solution: Matchsticks to Square

seanpgallivan — Wed, 16 Jun 2021 04:24:47 +0000

Leetcode Problem #473 (Medium): Matchsticks to Square

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Examples:

Example 1:

Input: matchsticks = [1,1,2,2,2]

Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Visual:

Example 2:

Input: matchsticks = [3,3,3,3,4]

Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Example 1:
Input:	matchsticks = [1,1,2,2,2]
Output:	true
Explanation:	You can form a square with length 2, one side of the square came two sticks with length 1.
Visual:

Example 2:
Input:	matchsticks = [3,3,3,3,4]
Output:	false
Explanation:	You cannot find a way to form a square with all the matchsticks.

Constraints:

1 <= matchsticks.length <= 15

0 <= matchsticks[i] <= 10^9

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

At first glance, this problem seems rather straightforward: find the total length of the matchsticks in M, figure out how long each side of the square must be, then find every combination of matchsticks that can add up to side. If four unique sets of matchsticks each add up to side, then we can return true.

The fact that the constraint upon the only imput is so low would seem to suggest that an O(2^N) solution is appropriate. There are, however, a few things we can do to optimize this process. The first key realization is that we can, in fact, use a greedy approach.

Consider the case of M = [1,1,1,2,2,2,3]. In this case, we can easily see that the total is 12 and thus side = 3. If we were to start iterating through M to find multiples of 3, we'd first group together the first three elements and then also find the last element, but be unable to make two more 3s from the middle elements of M. This would perhaps suggest that a greedy approach will not work, because it's readily apparent that we need to save the 1s to pair up with the 2s to make three of the four sides.

But that also suggests the solution, which is that we can use a greedy approach if we iterate through M in descending order. That way, each 2 will naturally seek out its matching 1 before we could ever attempt to match the 1s together in a less efficient manner.

That means that we can just use a recursive backtracking helper (btrack) to help find the side groups in M. But first, we can take care of some edge cases: If the total sum of M is not divisble by 4, or if any single matchstick in M is longer than the calculated side, then a solution is impossible and we should return false.

As for our recursive helper, it will need to iterate through the sorted M multiple times, attempting to build up groups that match side. We'll also keep track of how many groups we've found (done), and whenever we find a match, start btrack back at the beginning with done incremented.

(Note: When incrementing done and starting the recursive helper over, we can start at index 1 instead of index 0 because M[0] will always be a part of the first grouping.)

Once we've finished 3 groups, we can go ahead and return true, because we know that the remaining pieces must add up to side. If at any point we reach the end of M without finishing the current group, however, we should return false.

When attempting to add a piece to the current group, we can obviously skip pieces that are larger than the remaining space, as well as pieces that have already been used. Normally, this would require some kind of additional array or set to keep track of the used pieces, but we can use an in-place approach with M and just replace the used values with a value larger than side. This will simplify the check to skip elements to just one conditional.

(Note: If you don't want to modify the input, you could use a single integer and bit manipulation to achieve the same result in O(1) space. Sorting M will still take O(N) space if you don't want to modify M, however, and in any case, we'll be using O(N) space for the recursion stack.)

If an attempted piece turns out to be unsuccessfully and we're returned back up the recursion stack, we should remember to backtrack the current index (i) of M to its previous value (num).

Time Complexity: O(2^N) where N is the length of M for the attempted combinations of elements in M
Space Complexity: O(N) for the recursion stack

Implementation:

Java makes it more complicated to reverse sort a primitive array, so we can just use a simple sort and then iterate through M backwards instead.

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var makesquare = function(M) {
    let n = M.length, side = M.reduce((a,c) => a + c) / 4
    M.sort((a,b) => b - a)
    if (side !== ~~side || M[0] > side)
        return false
    const btrack = (i, space, done) => {
        if (done === 3)
            return true
        for (; i < n; i++) {
            let num = M[i], res
            if (num > space)
                continue
            M[i] = side + 1
            if (num === space)
                res = btrack(1, side, done+1)
            else
                res = btrack(i+1, space-num, done)
            if (res)
                return true
            M[i] = num
            while (M[i+1] === num)
                i++
        }
        return false
    }
    return btrack(0, side, 0)
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def makesquare(self, M: List[int]) -> bool:
        n, side = len(M), sum(M) / 4
        M.sort(reverse=True)
        if side != int(side) or M[0] > side:
            return False
        def btrack(i, space, done): 
            if done == 3:
                return True
            while i < n:
                num = M[i]
                if num > space:
                    i += 1
                    continue
                M[i] = side + 1
                if num == space:
                    res = btrack(1, side, done+1)
                else:
                    res = btrack(i+1, space-num, done)
                if res:
                    return True
                M[i] = num
                while i < n and M[i] == num:
                    i += 1
            return False
        return btrack(0, side, 0)

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public boolean makesquare(int[] M) {
        Arrays.sort(M);
        int total = 0;
        for (int i = 0; i < M.length; i++)
            total += M[i];
        side = total / 4;
        if ((float)total / 4 > side || M[M.length-1] > side)
            return false;
        return btrack(M.length-1, side, 0, M);
    }
    private int side;
    private boolean btrack(int i, int space, int done, int[] M) {
        if (done == 3)
            return true;
        for (; i >= 0; i--) {
            int num = M[i];
            boolean res;
            if (num > space)
                continue;
            M[i] = side + 1;
            if (num == space)
                res = btrack(M.length-2, side, done+1, M);
            else
                res = btrack(i-1, space-num, done, M);
            if (res)
                return true;
            M[i] = num;
            while (i > 0 && M[i-1] == num)
                i--;
        }
        return false;
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    bool makesquare(vector<int>& M) {
        sort(M.begin(), M.end(), greater<int>());
        int total = accumulate(M.begin(), M.end(), 0);
        side = total / 4;
        if ((float)total / 4 > side || M[0] > side)
            return false;
        return btrack(0, side, 0, M);
    }
private:
    int side;
    bool btrack(int i, int space, int done, vector<int>& M) {
        if (done == 3)
            return true;
        for (; i < M.size(); i++) {
            int num = M[i];
            bool res;
            if (num > space)
                continue;
            M[i] = side + 1;
            if (num == space)
                res = btrack(1, side, done+1, M);
            else
                res = btrack(i+1, space-num, done, M);
            if (res)
                return true;
            M[i] = num;
            while (i < M.size() and M[i+1] == num)
                i++;
        }
        return false;
    }
};

Solution: Maximum Units on a Truck

seanpgallivan — Mon, 14 Jun 2021 07:50:57 +0000

Leetcode Problem #1710 (Easy): Maximum Units on a Truck

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

numberOfBoxes i is the number of boxes of type i.

numberOfUnitsPerBox i is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Examples:

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4

Output: 8

Explanation: There are:

- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.

You can take all the boxes of the first and second types, and one box of the third type.

The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10

Output: 91

Example 1:
Input:	boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output:	8
Explanation:	There are: - 1 box of the first type that contains 3 units. - 2 boxes of the second type that contain 2 units each. - 3 boxes of the third type that contain 1 unit each. You can take all the boxes of the first and second types, and one box of the third type. The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2:
Input:	boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output:	91

Constraints:

1 <= boxTypes.length <= 1000

1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000

1 <= truckSize <= 10^6

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

For this problem, we simply need to prioritize the more valuable boxes first. To do this, we should sort the boxtypes array (B) in descending order by the number of units per box (B[i][1]).

Then we can iterate through B and at each step, we should add as many of the boxes as we can, until we reach the truck size (T). We should add the number of boxes added multiplied by the units per box to our answer (ans), and decrease T by the same number of boxes.

Once the truck is full (T == 0), or once the iteration is done, we should return ans.

Time Complexity: O(N log N) where N is the length of B, for the sort
Space Complexity: O(1)

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var maximumUnits = function(B, T) {
    B.sort((a,b) => b[1] - a[1])
    let ans = 0
    for (let i = 0; T && i < B.length; i++) {
        let count = Math.min(B[i][0], T)
        ans += count * B[i][1], T -= count
    }
    return ans
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def maximumUnits(self, B: List[List[int]], T: int) -> int:
        B.sort(key=lambda x: x[1], reverse=True)
        ans = 0
        for b,n in B:
            boxes = min(b, T)
            ans += boxes * n
            T -= boxes
            if T == 0: return ans
        return ans

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int maximumUnits(int[][] B, int T) {
        Arrays.sort(B, (a,b) -> b[1] - a[1]);
        int ans = 0;
        for (int[] b : B) {
            int count = Math.min(b[0], T);
            ans += count * b[1];
            T -= count;
            if (T == 0) return ans;
        }
        return ans;
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int maximumUnits(vector<vector<int>>& B, int T) {
        sort(B.begin(), B.end(), [](auto& a, auto& b) { return b[1] < a[1];});
        int ans = 0;
        for (auto& b : B) {
            int count = min(b[0], T);
            ans += count * b[1], T -= count;
            if (!T) return ans;
        }
        return ans;
    }
};

Solution: Palindrome Pairs

seanpgallivan — Sun, 13 Jun 2021 10:07:43 +0000

Leetcode Problem #336 (Hard): Palindrome Pairs

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.

Examples:

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]

Output: [[0,1],[1,0],[3,2],[2,4]]

Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: words = ["bat","tab","cat"]

Output: [[0,1],[1,0]]

Explanation: The palindromes are ["battab","tabbat"]

Example 3:

Input: words = ["a",""]

Output: [[0,1],[1,0]]

Example 1:
Input:	words = ["abcd","dcba","lls","s","sssll"]
Output:	[[0,1],[1,0],[3,2],[2,4]]
Explanation:	The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:
Input:	words = ["bat","tab","cat"]
Output:	[[0,1],[1,0]]
Explanation:	The palindromes are ["battab","tabbat"]

Example 3:
Input:	words = ["a",""]
Output:	[[0,1],[1,0]]

Constraints:

1 <= words.length <= 5000

0 <= words[i].length <= 300

words[i] consists of lower-case English letters.

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

A naive approach here would attempt every possible pairing of words, but that would be inefficient. Instead, we can figure out what possible words would pair with each word and specifically check for those.

To do this, we'll first have to store each word in a map structure (wmap), with the word as the key and the index as the value. This way, we can look up any possible matches with the current word as we iterate through words.

The next thing we'll want to do is define a helper function (isPal) to check if a word is a palindrome. Rather than having to pass it a substring of a word, we can define it to take a range of indexes to check, so that we're not constantly building new strings.

As we iterate through words, then, each word will possibly match another word in one of three ways:

A blank string word will match on either side with any palindrome word. (e.g. "" will match with "abc" and vice versa)
A full word will match on either side with its backwards version. (e.g. "abc" will match with "cba", and vice versa)
A partial word will match its backwards version on the opposite side if the leftover portion of the word is a palindrome (e.g. "abcddd" will match with "cba" because "abc" matches with "cba" and "ddd" is a palindrome)

The first check is easy to perform. If we find a blank string, we can iterate through the entire words list an extra time searching for palindromes to match. We just need to remember not to match the blank string with itself.

For the second check, since we'll eventually iterate to the matching full word, we should only add the one pair at this time, rather than both, as we'll be able to add the second ordering of the same pair when we get to the second word.

The third check is the most difficult. For this, we'll want to first reverse the current word to its backwards version (bw), since we'll be matching existing frontwards words in wmap. Then we should iterate through the indexes of the word itself, testing both sides of the dividing index (j) for being a palindrome.

If a palindrome is found, then we can attempt to lookup the other portion of the word in wmap. If a match is found, we can push that pair to our answer array (ans). At the end of the iteration of words, we can return ans.

Time Complexity: O(N * M^2) where N is the length of words and M is the average length of the words in words
Space Complexity: O(N) for wmap

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var palindromePairs = function(words) {
    let wmap = new Map(), ans = []
    for (let i = 0; i < words.length; i++)
        wmap.set(words[i], i)
    for (let i = 0; i < words.length; i++) {
        if (words[i] === "") {
            for (let j = 0; j < words.length; j++)
                if (isPal(words[j]) && j !== i)
                    ans.push([i, j], [j, i])
            continue
        }
        let bw = words[i].split("").reverse().join("")
        let res = wmap.get(bw)
        if (res !== undefined && res !== i)
            ans.push([i, res])
        for (let j = 1; j < bw.length; j++) {
            if (isPal(bw, 0, j - 1)) {
                let res = wmap.get(bw.slice(j))
                if (res !== undefined)
                    ans.push([i, res])
            }
            if (isPal(bw, j)) {
                let res = wmap.get(bw.slice(0,j))
                if (res !== undefined)
                    ans.push([res, i])
            }
        }
    }
    return ans
};

const isPal = (word, i=0, j=word.length-1) => {
    while (i < j)
        if (word[i++] !== word[j--]) return false
    return true
}

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        wmap, ans = {}, []
        for i in range(len(words)):
            wmap[words[i]] = i
        for i in range(len(words)):
            if words[i] == "":
                for j in range(len(words)):
                    w = words[j]
                    if self.isPal(w, 0, len(w)-1) and j != i:
                        ans.append([i, j])
                        ans.append([j, i])
                continue
            bw = words[i][::-1]
            if bw in wmap:
                res = wmap[bw]
                if res != i: ans.append([i, res])
            for j in range(1, len(bw)):
                if self.isPal(bw, 0, j - 1) and bw[j:] in wmap:
                    ans.append([i, wmap[bw[j:]]])
                if self.isPal(bw, j, len(bw)-1) and bw[:j] in wmap:
                    ans.append([wmap[bw[:j]], i])
        return ans

    def isPal(self, word: str, i: int, j: int) -> bool:
        while i < j:
            if word[i] != word[j]: return False
            i += 1
            j -= 1
        return True

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> wmap = new HashMap<>();
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++)
            wmap.put(words[i], i);
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals("")) {
                for (int j = 0; j < words.length; j++) {
                    String w = words[j];
                    if (isPal(w, 0, w.length()-1) && j != i) {
                        ans.add(List.of(i, j));
                        ans.add(List.of(j, i));
                    }
                }
                continue;
            }
            StringBuilder sb = new StringBuilder(words[i]);
            sb.reverse();
            String bw = sb.toString();
            if (wmap.containsKey(bw)) {
                int res = wmap.get(bw);
                if (res != i) ans.add(List.of(i, res));
            }
            for (int j = 1; j < bw.length(); j++) {
                if (isPal(bw, 0, j-1)) {
                    String s = bw.substring(j);
                    if (wmap.containsKey(s))
                        ans.add(List.of(i, wmap.get(s)));
                }
                if (isPal(bw, j, bw.length()-1)) {
                    String s = bw.substring(0,j);
                    if (wmap.containsKey(s))
                        ans.add(List.of(wmap.get(s), i));
                }
            }
        }
        return ans;
    }

    private boolean isPal(String word, int i, int j) {
        while (i < j)
            if (word.charAt(i++) != word.charAt(j--)) return false;
        return true;
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string, int> wmap;
        vector<vector<int>> ans;
        for (int i = 0; i < words.size(); i++)
            wmap[words[i]] = i;
        for (int i = 0; i < words.size(); i++) {
            if (words[i] == "") {
                for (int j = 0; j < words.size(); j++) {
                    string& w = words[j];
                    if (isPal(w, 0, w.size()-1) && j != i) {
                        ans.push_back(vector<int> {i, j});
                        ans.push_back(vector<int> {j, i});
                    }
                }
                continue;
            }
            string bw = words[i];
            reverse(bw.begin(), bw.end());
            if (wmap.find(bw) != wmap.end()) {
                int res = wmap[bw];
                if (res != i) ans.push_back(vector<int> {i, res});
            }
            for (int j = 1; j < bw.size(); j++) {
                if (isPal(bw, 0, j-1)) {
                    string s = bw.substr(j, bw.size()-j);
                    if (wmap.find(s) != wmap.end())
                        ans.push_back(vector<int> {i, wmap[s]});
                }
                if (isPal(bw, j, bw.size()-1)) {
                    string s = bw.substr(0, j);
                    if (wmap.find(s) != wmap.end())
                        ans.push_back(vector<int> {wmap[s], i});
                }
            }
        }
        return ans;
    }

private:
    bool isPal(string& word, int i, int j) {
        while (i < j)
            if (word[i++] != word[j--]) return false;
        return true;
    }
};

Solution: Minimum Number of Refueling Stops

seanpgallivan — Sat, 12 Jun 2021 21:17:03 +0000

Leetcode Problem #871 (Hard): Minimum Number of Refueling Stops

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

A car travels from a starting position to a destination which is target miles east of the starting position.

Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Examples:

Example 1:

Input: target = 1, startFuel = 1, stations = []

Output: 0

Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]

Output: -1

Explanation: We can't reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]

Output: 2

Explanation: We start with 10 liters of fuel.

We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas.

Then, we drive from position 10 to position 60 (expending 50 liters of fuel), and refuel from 10 liters to 50 liters of gas.

We then drive to and reach the target.

We made 2 refueling stops along the way, so we return 2.

Example 1:
Input:	target = 1, startFuel = 1, stations = []
Output:	0
Explanation:	We can reach the target without refueling.

Example 2:
Input:	target = 100, startFuel = 1, stations = [[10,100]]
Output:	-1
Explanation:	We can't reach the target (or even the first gas station).

Example 3:
Input:	target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output:	2
Explanation:	We start with 10 liters of fuel. We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas. Then, we drive from position 10 to position 60 (expending 50 liters of fuel), and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target. We made 2 refueling stops along the way, so we return 2.

Constraints:

1 <= target, startFuel, stations[i][1] <= 10^9

0 <= stations.length <= 500

0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

Since this problem is asking for the least amount of refuelings, we should attempt a greedy approach to the solution. To accomplish that, we should start with 0 refuelings and keep attempting one additional refueling until we find a working solution.

In a naive approach, we would attempt every single combination of 1 refueling station, then every single combination of 2 refueling stations, etc., but that would take way too long.

Instead, let's consider the natural progression of iterating through the list of stations (S). At each station (S[i]) we should first check to see if we have enough fuel to get there.

(Note: Since the station distances are measured in distance from the start, not distance from the last station, it's easier to keep track of the total fuel obtained (F), rather than the unspent fuel, because we can directly compare that to the distance traveled (dist).)

If we didn't have enough fuel to get to the current station, then we should have refueled somewhere. Only a station seen before S[i] is available for this retroactive refueling, however, so we need to choose a prior station at which to have refueled. Given our choice, we should naturally pick the station with the largest reserve of fuel.

Rather than attempting to sort a portion of S each time, we should instead use a max priority queue (or max heap) (pq/heap) to store the previously visited stations' fuel reserves so that we can always choose the ideal station at any point along our iteration.

When we find ourselves unable to reach the next station, we should continue to pull fuel reserves from pq until we have enough. If we run out of reserves while F < dist, then we can never reach the target (T), and should return -1.

We should also keep track of the total number of times (ans) we've removed fuel from the reserves in pq, and iterate one extra time to reach T from the last station. Upon successfully reaching T, we can return ans.

Time Complexity: O(N log N) where N is the length of S, for up to N insertions and N removals from pq/heap
Space Complexity: O(N) for pq/heap

Implementation:

Javascript's MaxPriorityQueue() npm is easier to use than, but not as efficient as, a custom max heap implementation. Both are included below for comparison.

Python defaults to a min heap, so we can reverse the signs upon insertion and extraction to achieve an effective max heap implementation.

Javascript Code:

(Jump to: Problem Description || Solution Idea)
w/ MaxPriorityQueue():

var minRefuelStops = function(T, F, S) {
    let n = S.length, pq = new MaxPriorityQueue(), ans = 0
    for (let i = 0; i <= n; i++) {
        let dist = i === n ? T : S[i][0]
        while (F < dist) {
            if (!pq.size()) return -1
            F += pq.dequeue().element, ans++
        }
        if (i < n) pq.enqueue(S[i][1])
    }
    return ans
};

w/ custom Max Heap:

var minRefuelStops = function(T, F, S) {
    let n = S.length, ans = 0

    // custom Max Heap implementation
    let heap = [,]
    const hpush = val => {
        let i = heap.length, par = i >> 1, temp
        heap.push(val)
        while (heap[par] < heap[i]) {
            temp = heap[par], heap[par] = heap[i], heap[i] = temp
            i = par, par = i >> 1
        }
    }
    const hpop = () => {
        if (heap.length === 1) return null
        let top = heap[1], left, right, temp,
            i = 1, child = heap[3] > heap[2] ? 3 : 2
        if (heap.length > 2) heap[1] = heap.pop()
        else heap.pop()
        while (heap[i] < heap[child]) {
            temp = heap[child], heap[child] = heap[i], heap[i] = temp
            i = child, left = i << 1, right = left + 1
            child = heap[right] > heap[left] ? right : left
        }
        return top
    }

    for (let i = 0; i <= n; i++) {
        let dist = i === n ? T : S[i][0]
        while (F < dist) {
            if (heap.length === 1) return -1
            F += hpop(), ans++
        }
        if (i < n) hpush(S[i][1])
    }
    return ans
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def minRefuelStops(self, T: int, F: int, S: List[List[int]]) -> int:
        n, heap, ans = len(S), [], 0
        for i in range(n+1):
            dist = T if i == n else S[i][0]
            while F < dist:
                if len(heap) == 0: return -1
                F -= heappop(heap)
                ans += 1
            if i < n: heappush(heap, -S[i][1])
        return ans

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int minRefuelStops(int T, int F, int[][] S) {
        int n = S.length, ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
        for (int i = 0; i <= n; i++) {
            int dist = i == n ? T : S[i][0];
            while (F < dist) {
                if (pq.size() == 0) return -1;
                F += pq.poll();
                ans++;
            }
            if (i < n) pq.add(S[i][1]);
        }
        return ans;
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int minRefuelStops(int T, int F, vector<vector<int>>& S) {
        int n = S.size(), ans = 0;
        priority_queue<int> pq;
        for (int i = 0; i <= n; i++) {
            int dist = i == n ? T : S[i][0];
            while (F < dist) {
                if (!pq.size()) return -1;
                F += pq.top(), ans++;
                pq.pop();
            }
            if (i < n) pq.push(S[i][1]);
        }
        return ans;
    }
};

Solution: Stone Game VII

seanpgallivan — Fri, 11 Jun 2021 09:08:33 +0000

Leetcode Problem #1690 (Medium): Stone Game VII

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones' values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score's difference. Alice's goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob's score if they both play optimally.

Examples:

Example 1:

Input: stones = [5,3,1,4,2]

Output: 6

Explanation: - Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.

Example 2:

Input: stones = [7,90,5,1,100,10,10,2]

Output: 122

Example 1:
Input:	stones = [5,3,1,4,2]
Output:	6
Explanation:	- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4]. - Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4]. - Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4]. - Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4]. - Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = []. The score difference is 18 - 12 = 6.

Example 2:
Input:	stones = [7,90,5,1,100,10,10,2]
Output:	122

Constraints:

n == stones.length

2 <= n <= 1000

1 <= stones[i] <= 1000

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

Like most of the Stone Game problems, this one boils down to a system of ever-repeating subproblems, as the there are many different ways to get to the same board condition as we move towards the end of the game. This naturally points to a dynamic programming (DP) solution.

In order to represent the different board positions, we'd normally build an N * N DP matrix where N is the length of the stones array (S). In this DP array, dp[i][j] would represent the best score difference with i representing the leftmost remaining stone's index and j representing the rightmost remaining stone's index.

We'll start at i = N - 2 and iterate backwards and start each nested for loop at j = i + 1. This ensures that we're building the pyramid of DP results downward, always starting each row with i and j next to each other.

For each row, we'll keep track of the sum total of the stones in the range [i,j] by adding S[j] at each iteration of j. Then, we can represent the current player's ideal play by choosing the best value between picking the stone at i (total - S[i]) and picking the stone at j (total - S[j]). For each option, we have to also subtract the best value that the other player will get from the resulting board position (dp[i+1][j] or dp[i][j-1]).

Since we will only be building off the cells to the left and above the current cell, however, we can actually eliminate the DP matrix and instead just one array representing the current row, reusing it each time. This will drop the space complexity from O(N^2) to O(N).

This approach works because, when evaluating a new cell, the cell to the left will already have been overwritten and will accurately represent the previous cell on the same row. The not-yet-overwritten current cell value still represents the cell that would have been in the row above in a full DP matrix.

At the end, the solution will be the value stored in the DP array representing the board position with all stones present. We should therefore return dp[N-1].

Time Complexity: O(N^2) where N is the length of S
Space Complexity: O(N) for dp

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var stoneGameVII = function(S) {
    let N = S.length, dp = new Uint32Array(N)
    for (let i = N - 2; ~i; i--) {
        let total = S[i]
        for (let j = i + 1; j < N; j++) {
            total += S[j]
            dp[j] = Math.max(total - S[i] - dp[j], total - S[j] - dp[j-1])
        }
    }
    return dp[N-1]
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def stoneGameVII(self, S: List[int]) -> int:
        N, dp = len(S), [0] * len(S)
        for i in range(N - 2, -1, -1):
            total = S[i]
            for j in range(i + 1, N):
                total += S[j]
                dp[j] = max(total - S[i] - dp[j], total - S[j] - dp[j-1])
        return dp[-1]

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int stoneGameVII(int[] S) {
        int N = S.length;
        int[] dp = new int[N];
        for (int i = N - 2; i >= 0; i--) {
            int total = S[i];
            for (int j = i + 1; j < N; j++) {
                total += S[j];
                dp[j] = Math.max(total - S[i] - dp[j], total - S[j] - dp[j-1]);
            }
        }
        return dp[N-1];
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int stoneGameVII(vector<int>& S) {
        int N = S.size();
        vector<int> dp(N);
        for (int i = N - 2; ~i; i--) {
            int total = S[i];
            for (int j = i + 1; j < N; j++) {
                total += S[j];
                dp[j] = max(total - S[i] - dp[j], total - S[j] - dp[j-1]);
            }
        }
        return dp[N-1];
    }
};

Solution: My Calendar I

seanpgallivan — Thu, 10 Jun 2021 09:04:50 +0000

Leetcode Problem #729 (Medium): My Calendar I

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Examples:

Example 1:

Input: MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true

Explanation: The first event can be booked.
The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

Example 1:
Input:	MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(15, 25); // returns false MyCalendar.book(20, 30); // returns true
Explanation:	The first event can be booked. The second can't because time 15 is already booked by another event. The third event can be booked, as the first event takes every time less than 20, but not including 20.

Constraints:

The number of calls to MyCalendar.book per test case will be at most 1000.

In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

Since the bookings are not allowed to overlap, we'll naturally need to keep the data sorted in some way so that we can find the proper insertion position of each new booking, and to check for the validity of the booking.

The naive solution here would be to use an array and resort it each time, at a time complexity of O(N * log N). Alternately, we could use a binary search to find the right position, then insert the booking at that position, but that would take O(log N) time for the binary search and another O(N) time for the insertion.

(Important Note: Apparently, each of the four languages except Javascript has a sorted data structure based on a red-black tree structure which allows for insertion in only O(log N) time, rather than the O(N) time it would take for a standard array insertion. This, combined with the O(log N) time for the binary search makes this approach faster than a linked list approach. See the updated section below for the explanation.)

Python, Java, & C++:
Python, Java, and C++ allow for a sorted data structure with only a O(log N) insertion. In this approach, we first use a binary search function to find the proper insertion position, then compare the start and end of the new booking to the existing calendar entries to check for the validity of the new booking.

To avoid having to compare more than one calender entry for validation (as finding another entry might take another O(log N) time), we can store the entries in reverse order in calendar ({end, start}), then find the upper bound of the booking using the proper order ({start, end}).

Let's consider a booking gap that looks like this:

  |---------|               |---------|

If we're comparing start vs start in our binary search, we could end up with the following scenarios:

  S---------|               S---------|
   <----------------------->                 // binary search range
       S---------|                           // possibility #1
               S---------|                   // possibility #2
                       S---------|           // possibility #3

This means that we'll have to access both surrounding bookings to check if the new booking clears both the previous booking's end and the next booking's start. If, instead, we store the bookings with start and end flipped, the binary search will automatically clear the previous booking's end, which means those three scenarios shift to this:

  |---------E               |---------E
             <----------------------->       // binary search range
               S---------|                   // possibility #1
                       S---------|           // possibility #2
                                 S---------| // possibility #3

This means that we only have to access the booking returned by the binary search, saving us the O(log N) time for the second lookup, as well as only requiring a single conditional check (new.end <= next.start), rather than two.

If the booking is invalid, we can return false, otherwise we can insert the new booking into calendar (in reverse order) and then return true. We can also insert a tail booking upon the calendar initialization to make the comparisons easier.

Javascript:
For Javascript, we can use a linked list approach, as searching the linked list will only be O(N) time and the insertion will only be O(1) time. We should start by defining our empty bookings list (head) with a head node and a tail node as bookends for the booking data.

For the book function, we will then iterate through the linked list until we find the booking that begins after our attempted booking start (curr). We should also remember to keep track of the last node, as well, so that we can stitch the new booking into the list.

Once we've located the proper node, we should check to see if the new booking will overlap, and return false if it does. Otherwise, we should create our new node, and insert it between last and curr, then return true.

Time Complexity:
- single booking w/ sorted tree: O(log N) where N is the length of the calendar
- single booking w/ linked list: O(N)
- complete series w/ sorted tree: O(N * log N)
- complete series w/ linked list: O(N^2)
Space Complexity: O(N) for the calendar

Javascript Code:

(Jump to: Problem Description || Solution Idea)
w/ Linked List:

class MyCalendar {
    constructor() {
        this.calendar = {start: -1, end: -1, next: {start: Infinity, end: Infinity}}
    }
    book = function(start, end) {
        let curr = this.calendar, last = curr
        while (start >= curr.end)
            last = curr, curr = curr.next
        if (curr.start < end)
            return false
        last.next = {start: start, end: end, next: curr}
        return true
    };
}

Python Code:

(Jump to: Problem Description || Solution Idea)
w/ SortedDict:

from sortedcontainers import SortedDict
class MyCalendar:
    def __init__(self):
        self.calendar = SortedDict({float('inf'):float('inf')})        
    def book(self, start: int, end: int) -> bool:
        ix = self.calendar.bisect_right(start)
        k,v = self.calendar.peekitem(ix)
        res = end <= v
        if res: self.calendar[end] = start
        return res

w/ Linked List:

class MyCalendar:
    def __init__(self):
        self.calendar = {'start': -1, 'end': -1, 'next': {'start': float('inf'), 'end': float('inf')}}
    def book(self, start: int, end: int) -> bool:
        curr = self.calendar
        while start >= curr['end']:
            last, curr = curr, curr['next']
        if curr['start'] < end:
            return False
        last['next'] = {'start': start, 'end': end, 'next': curr}
        return True

Java Code:

(Jump to: Problem Description || Solution Idea)
w/ TreeMap:

class MyCalendar {
    TreeMap<Integer,Integer> calendar = new TreeMap<>();
    public MyCalendar() {
        calendar.put(Integer.MAX_VALUE, Integer.MAX_VALUE);
    }
    public boolean book(int start, int end) {
        Map.Entry<Integer,Integer> pair = calendar.higherEntry(start);
        boolean res = end <= pair.getValue();
        if (res) calendar.put(end, start);
        return res;
    }
}

w/ Linked List:

class ListNode {
    public int start, end;
    public ListNode next;
    public ListNode(int s, int e, ListNode n) {
        start = s;
        end = e;
        next = n;
    }
}

class MyCalendar {
    ListNode calendar;
    public MyCalendar() {
        ListNode tail = new ListNode(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
        calendar = new ListNode(-1, -1, tail);
    }

    public boolean book(int start, int end) {
        ListNode curr = calendar, last = curr;
        while (start >= curr.end) {
            last = curr;
            curr = curr.next;
        }
        if (curr.start < end)
            return false;
        last.next = new ListNode(start, end, curr);
        return true;
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)
w/ Set:

class MyCalendar {
public:
    set<pair<int, int>> calendar = {{INT_MAX, INT_MAX}};
    bool book(int start, int end) {
        auto pair = calendar.upper_bound({start, end});
        bool res = end <= pair->second;
        if (res) calendar.insert({end, start});
        return res;
    }
};

w/ Linked List:

struct LNode {
public:
    int start, end;
    LNode* next;

    LNode(int s, int e, LNode* n) {
        start = s;
        end = e;
        next = n;
    }
};

class MyCalendar {
public:
    MyCalendar() {
        LNode* tail = new LNode(INT_MAX, INT_MAX, nullptr);
        calendar = new LNode(-1, -1, tail);
    }

    bool book(int start, int end) {
        LNode* curr = calendar, *last = curr;
        while (start >= curr->end)
            last = curr, curr = curr->next;
        if (curr->start < end)
            return false;
        last->next = new LNode(start, end, curr);
        return true;
    }
private:
    LNode* calendar;
};