[Programming]leetcode 128. Longest Consecutive Sequence

This is a solution of leetcode 128. Longest Consecutive Sequence.

Analysis

The target here is to find the longest consecutive interval using the integers from a given array and return its length.

Using the brutal force approach, we can sort this array and use a sliding window to find all the consecutive intervals and write down the longest length. The time complexity of array sorting would be normally $O(n\log n)$, and the time complexity of retrieving all the intervals would be $O(n)$. So, the total time complexity would be their sum, $O(n\log n)$.

Instead of listing all the consecutive intervals by sorting the array, we can try to calculate the length of the interval in which an element lays while we retrieve these numbers. We can use a dictionary to store an element as its key and the length of the consecutive interval in which it lays as its value.

Supposes we now have an integer $x$ from the array. If it is already in the dictionary, we don’t need to do anything, we can just move on to the next number. But if it is not in the dictionary, there would be 3 circumstances after we add it to the dictionary,

a) either $x-1$ or $x+1$ is in the dictionary

In this circumstance, adding $x$ into the dictionary can extend the interval ending with $x-1$ or the interval starting with $x+1$, these intervals length should be increased by 1.

b) both $x-1$ and $x+1$ are in the dictionary

In this circumstance, adding $x$ into the dictionary will combine the interval ending with $x-1$ and the interval starting with $x+1$ into a new bigger interval. The length of this new interval should be the sum of these small intervals’ length and also increased by 1.

c) neither $x-1$ nor $x+1$ is in the dictionary

In this circumstance, adding $x$ into the dictionary won’t affect other intervals, so its own length would be 1.

When we update the length of intervals, we need to update both the start and the end of the interval. We don’t need to update other elements in the interval, because when we add new numbers to the dictionary, we only take the end points of the interval into consideration.

Due to we only retrieve each element once, and the time complexity of reading or updating a dictionary is $O(1)$, the total time complexity of this solution would be $O(n)$.

Now, we can write the code.

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hash_dict = dict()
        
        max_length = 0
        for num in nums:
            if num not in hash_dict:
                left = hash_dict.get(num - 1, 0)
                right = hash_dict.get(num + 1, 0)
                
                cur_length = 1 + left + right
                if cur_length > max_length:
                    max_length = cur_length
                
                hash_dict[num] = cur_length
                hash_dict[num - left] = cur_length
                hash_dict[num + right] = cur_length
                
        return max_length

[Programming]leetcode 54. Spiral Matrix

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

[Programming]leetcode 36. Valid Sudoku

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

                

[Programming]leetcode 134. Gas Station

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