This is a solution of leetcode 54. Spiral Matrix.

Analysis

This question is not difficult, you just need to take special instances into consideration.

There are four steps in each loop,

1. print from left to right in the top row
2. print from up to down in the right col
3. print from right to left in the bottom row
4. print from down to up in the left col

Before step 3 and step 4, we need to check if there is still row or col left because the first two steps have cut a row from the top and a col from the right. If you miss this check, you may print duplicated elements.

Now we can write the code.

Code

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return list()
        
        rows, columns = len(matrix), len(matrix[0])
        order = list()
        left, right, top, bottom = 0, columns - 1, 0, rows - 1
        while left <= right and top <= bottom:
            for column in range(left, right + 1):
                order.append(matrix[top][column])
            for row in range(top + 1, bottom + 1):
                order.append(matrix[row][right])
            if left < right and top < bottom:
                for column in range(right - 1, left, -1):
                    order.append(matrix[bottom][column])
                for row in range(bottom, top, -1):
                    order.append(matrix[row][left])
            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
        return order

This is a solution of 36. Valid Sudoku.

Analysis

The target here is to check if a given board is a valid sudoku. The criteria are listed below,

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A brutal force solution would be retrieving each position on the board and checking if the element in that position has violated those three rules.

We could use 1 matrix to remember the appearance times for each number from 1 – 9 in each row. The same method can apply to column check and grid check too. So we will need 3 matrices. The grid will be indexed for 0 – 8 and mapped to the grid matrix rows. The map equation for position (i, j) would be that

$$grid\_row = (i // 3) * 3 + j // 3$$

Then we can write the code.

Code

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[0] * 9 for _ in range(9)]
        col = [[0] * 9 for _ in range(9)]
        grid = [[0] * 9 for _ in range(9)]

        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = int(board[i][j]) - 1
                    grid_row = (i // 3) * 3 + j // 3
                    if row[i][num] == 1 or col[j][num] == 1 or grid[grid_row][num] == 1:
                        return False
                    row[i][num] = col[j][num] = grid[grid_row][num] = 1
        return True

                

This is a solution for leetcode question 134. Gas Station.

Analysis

The target here is to find out if there is a starting point based on the given arrays that could let us go through all these gas stations one by one and back to the starting point in a round. And if it is, return the starting point’s index.

We can solve this question by brutal force. We can try to start at each station and check if we can pass all the stations and back to where we started. The time complexity would be $O(n^2)$ where $n$ is the length of the array.

But that’s pretty slow. So how can we speed it up?

Let’s suppose that we started at station $i$, and we arrive at station $j$ at the moment where,

$$remained\_gas_{i,j} + gas_j < cost_j \tag{1} \label{eq1}$$

The $remained\_gas_{i,j}$ denotes the remained gas when we start from $i$ and arrive at $j$. This means that we are not going to station $j+1$ because we are short of gas, and the starting point would not be $i$.

But how about the stations between $i$ and $j$, are they still possible to be a starting point?

Let’s say we have a station $x$ at somewhere between $i$ and $j$, and when we arrive at $j$ from $x$ we have

$$remained\_gas_{x, j} + gas_j \geq cost_j \tag{2}$$

which means we can go to $j+1$ from $x$. As we know we can arrive at $j$ from $i$, so we definitely can arrive at $x$ from $i$. And it’s obvious that when we arrive at $x$ from $i$, $remained\_gas_{i, x} \geq 0$ otherwise we won’t be able to arrive at $x$. So plus the remained gas from $i$ to $x$, we have

$$remained\_gas_{i,j} + gas_j = remained\_gas_{i,x} + remained\_gas_{x, j} + gas_j \geq cost_j \tag{3} $$

It conflicts with the given condition in $\eqref{eq1}$, so the hypothesis would be false. There will be no station $x$ in between $i$ and $j$ can be a possible starting point. Thus we can skip all the stations in between $i$ and $j$, and use $j+1$ as the new starting point and check if we can arrive at the end from there. The time complexity of this process would be $O(n)$.

We have reduced the time complexity from $O(n^2)$ to $O(n)$, but this only gives a possible starting point, not a definite answer. Because we only computed if we can arrive at the end of the arrays, which is the station $n-1$, but we don’t know if we can go through station $0$ to station $j – 1$ from station $n – 1$ with the remained gas we have.

Supposes the final candidate is station $j$. One possible way to find out if that’s the correct answer is to continue checking if we can arrive at the station $j-1$. And if we can, the answer will be $j$, otherwise, there is no answer to meet the question’s requirements. This process’s time complexity will be $O(j-1)$, and at its worst, it will be $O(n)$, so the total time complexity will be $O(n)$.

Seems like we have a good approach here, but let’s think about this. Is it really needed to go from the beginning and check if we can go through these stations in a second round?

The answer would be no.

When we find the candidate station $j$, we have already checked stations $0$ to $j – 1$, and they are not eligible. Assume that we have changed the starting point for $m$ times, and finally, we chose $j$. So the previous starting points would be a subarray of $0$ to $j-1$, and we can denote all the intervals’ end points as a vector $X$,

$$X = [x_0, x_1, …, x_{m}] \tag{4}$$

$$0 \leq x_k \leq j \tag{5}$$

$$0 \leq k \leq m \tag{6}$$

$$x_0 = 0, x_m = j \tag{7}$$

So at each interval, there is

$$remained\_gas_{x_i, x_{i+1}} \lt 0 \tag{8}$$

$$ 0 \leq i \leq m-1 \tag{9}$$

So if the $remained\_gas_{j, n-1} + \sum_{0 \leq i \leq m-1}{remained\_gas_{x_i,x_{i+1}}} \lt 0$, we can not go back to $j$, therefore there is no possible answer. And these values can be calculated as below.

$$\begin{align}
\sum_{0 \leq i \leq m}{remained\_gas_{x_i,x_{i+1}}} &= \sum_{0 \leq i \leq m-1}{\sum_{x_i \leq k \leq x_{i+1}}{gas_k – cost_k}} \\
&= \sum_{x_0 \leq k \leq x_m}{gas_k – cost_k} \\
&= \sum_{0 \leq k \leq j}{gas_k – cost_k} \\
\end{align} \tag{10} \label{eq2}$$

$$remained\_gas_{j, n-1} = \sum_{j \leq i \leq n-1}{gas_i – cost_i} \tag{11} \label{eq3}$$

So combine $\eqref{eq2}$ and $\eqref{eq3}$,

$$\begin{align}
& remained\_gas_{j, n-1} + \sum_{0 \leq i \leq m-1}{remained\_gas_{x_i,x_{i+1}}} \\ &= \sum_{0 \leq k \leq j}{gas_k – cost_k} + \sum_{j \leq i \leq n-1}{gas_i – cost_i} \\
&= \sum_{0 \leq k \leq n-1}{gas_k – cost_k} \\
\end{align} \tag{12} \label{eq4}$$

Turns out it is just the sum of the value of gas minus cost at each station, and it can be calculated in the first round. By now we have got the final approach, and we can write the code.

Code

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        start = 0
        remained_gas = 0
        total_remained_gas = 0
        for i in range(len(gas)):
            remained_gas += gas[i] - cost[i]
            total_remained_gas += gas[i] - cost[i]
            if remained_gas <= 0:
                remained_gas = 0
                start = i + 1
        if total_remained_gas < 0: return -1
        return start