[LeetCode] 72. Edit Distance

Problem : https://leetcode.com/problems/edit-distance/

Below implementation uses top-down based solution to find the minimum number of operation.

Let distance(i, j) = minimum operations to transform word1[ 0 : i ] to word2 [0 : j ].

There are 3 ways to construct word2[0:j] 

word2[0:j] = distance(i - 1, j) + 1       # delete character word1[i-1]

word2[0:j] = distance(i, j - 1) + 1       # insert character word2[j-1]  

word2[0:j] = distance(i - 1, j - 1)        # if word1[i-1] == word2[j-1]

word2[0:j] = distance(i - 1, j - 1)  + 1 # if word1[i-1] != word2[j-1], replace word1[i-1] with word2[j-1]

distance(i, j) = minimum operation of those 3 ways

from functools import lru_cache

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        
        @lru_cache(maxsize = None)
        def distance(i, j):
            if i == 0:
                return j
            
            if j == 0:
                return i
            
            # delete
            d1 = distance(i-1, j) + 1
            
            # insert
            d2 = distance(i, j-1) + 1
                        
            d3 = distance(i-1, j-1)
            # replace
            if word1[i-1] != word2[j-1]:
                d3 += 1
            
            return min(d1, d2, d3)
        
        return distance(len(word1), len(word2))

[LeetCode] 71. Simplify Path

Problem : https://leetcode.com/problems/simplify-path/

class Solution {
    public String simplifyPath(String path) {
        Deque<String> deque = new LinkedList<>();
        StringBuilder token = new StringBuilder();
        
        if (path.charAt(path.length()-1) != '/') {
            path += "/";
        }
        
        for (char c : path.toCharArray()) {
            if (c == '/') {
                if ( ".".equals(token.toString()) || token.length() == 0) {
                    // do nothing
                } else if ("..".equals(token.toString())) {
                    if (!deque.isEmpty()) {
                        deque.pollLast();
                    }
                } else {
                    deque.offerLast(token.toString());
                }
                // reset the token 
                token.setLength(0);
            } else {
                token.append(c);
            }
        }
        
        StringBuilder result = new StringBuilder();
        
        while (!deque.isEmpty()) {
            result.append("/");
            result.append(deque.pollFirst());
        }
        
        return result.length() != 0 ? result.toString() : "/";      
    }
}

Edited on 03/13/2022. Use deque to push / pop from the rear and pop in the front of the intermediate 'directory name' list.

[LeetCode] 70. Climbing Stairs

Problem : https://leetcode.com/problems/climbing-stairs/

Let  stairs(x) = steps to reach stair x.

We can either reach to stair x by climb 1 step from stair x - 1, or climb 2 steps from stair x - 2. 

stairs(x) = stair(x-1) + stair(x-2)

Obviously,  stair(1) = 1 and stair(2) = 2

Below is a memorization based implementation.

Time Complexity : O ( N )

The top-down solution:

class Solution:
    def climbStairs(self, n: int) -> int:
        
        @cache
        def stairs(x): 
            return stairs(x-1) + stairs(x-2) if x > 2 else x
        
        return stairs(n)

The bottom-up solution:

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 0, 1    
        for _ in range(n):
            a, b = b, a + b
        
        return b

Edited on 10/05/2021. Update the top-down and buttom-up solutions.

[LeetCode] 69. Sqrt(x)

Problem : https://leetcode.com/problems/sqrtx/

Use binary search to locate square root in (0, x). 

Since problem statement requests to truncate decimal part, the code needs to return 'right - 1'.  Binary search's 'left' is the lower boundary and 'right' is the upper boundary.

Time complexity : O ( Log(X) )

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
 
        left, right = 0, x
        
        while left < right:
            mid = left + (right - left) // 2
            
            if mid * mid == x:
                return mid
            
            if mid * mid > x:
                right = mid
            else:
                left = mid + 1
        
        return right - 1 if x > 1 else x

[LeetCode] 68. Text Justification

Problem : https://leetcode.com/problems/text-justification/

As the problem statement mentioned, the code needs to try to pack as many words as possible on one row. 

There is at least one space character between each word. 

So the shortest length of row

 =  total length of all words +  1 space between each word 

 =  total length of all words + (number of word + 1). 

We need to add word to next row if even shortest possible length exceeds the max row width threshold.

from functools import reduce

class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        
        def width(row):
            """
            calculate row width with 1 space between each word
            """
            return reduce(lambda x, y: x + len(y), row, 0) + len(row) - 1
            
            
        def justify(row, leftJustified):
            """
            justify text on this row 
            """
            
            if len(row) == 1:
                return row[0] + ' ' * (maxWidth - len(row[0]))

            line = ""
            
            rowSize = reduce(lambda x, y: x + len(y), row, 0)
            space = (maxWidth - rowSize) // (len(row) - 1) 
            extraSpace = (maxWidth - rowSize) % (len(row) - 1)
            
            if not leftJustified:
                for i in range(len(row)):
                    line += row[i]
                    
                    if i < len(row) - 1:
                        if extraSpace > 0:
                            # add extra spaces as evenly as possible
                            line += ' ' * (space + 1)
                            extraSpace -= 1
                        else:
                            line += ' ' * space
            else:
                for i in range(len(row)):
                    line += row[i]
                    if i < len(row) -1:
                        line += ' '

                line += ' ' * (maxWidth - len(line))

            return line
            
        
        rows = []
        for w in words:
            if not rows:
                rows.append([w])
                continue
            
            if width(rows[-1]) + len(w) + 1 <= maxWidth:
                # pack as many words as possible to one line
                rows[-1].append(w)
            else:
                rows.append([w])
        
        result = []
        for i in range(len(rows)):
            result.append(justify(rows[i], i == len(rows) - 1))
            
        return result

[LeetCode] 67. Add Binary

Problem : https://leetcode.com/problems/add-binary/ 

Similar to problem 66. Plus One .

Simulate long addition process. Remember to handle the last carry when it is greater than zero.

Time Complexity = O ( M + N ).  M = length of a, N = length of b.

class Solution {
    public String addBinary(String a, String b) {
        int n = Math.max(a.length(), b.length()) + 1;
        char[] buffer = new char[n];

        int i = a.length() - 1;
        int j = b.length() - 1;
        int k = n - 1;

        int carry = 0;

        while (i >= 0 || j >= 0 || carry == 1) {
            int A =  i >= 0 ? a.charAt(i--) - '0' : 0;
            int B =  j >= 0 ? b.charAt(j--) - '0' : 0;
            buffer[k--] = (char)('0' + (A + B + carry) % 2);
            carry = (A + B + carry) / 2;
        }
       
        
        if (buffer[0] != 0) {
            return new String(buffer);
        }

        return new String(Arrays.copyOfRange(buffer, 1, n));
    }
}

Edited on 02/13/2023. Replace with an optimized Java version solution.

Edited on 01/09/2022. Replace with the Java version solution.

[LeetCode] 66. Plus One

Problem : https://leetcode.com/problems/plus-one/

Simulate long addition process. Remember to handle the last carry when it is greater than zero.

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        result = [0] * (len(digits) + 1)
        i = len(digits) - 1
        j = i + 1
        
        carry = 1
        
        while i >= 0 or carry > 0:
            if i >= 0:
                result[j] = (digits[i] + carry) % 10
                carry = (digits[i] + carry) // 10
                i -= 1
                j -= 1
            else:
                result[j] = carry
                j -= 1
                carry = 0
        
        return result if j == -1 else result[j+1:]

[LeetCode] 65. Valid Number

Problem : https://leetcode.com/problems/valid-number/

Not hard but annoying.  Use FSM to check if character is allowed in the current state.

class Solution:
    def isNumber(self, s: str) -> bool:
        
        state = 'sign'
        
        for w in s:   
            if state == 'sign':
                if w in '+-':
                    state = 'integer_start'
                    continue
                
                if w.isdigit():
                    state = 'integer'
                    continue
                
                if w == '.':
                    state = 'decimal_start'
                    continue
            
                return False
            
            if state == 'integer_start':
                if w.isdigit():
                    state = 'integer'
                    continue
                
                if w == '.':
                    state = 'decimal_start'
                    continue
                       
                return False
            
            if state == 'integer':
                
                if w.isdigit():
                    continue
                    
                if w in 'eE':
                    state = 'sign_e'
                    continue
                
                if w == '.':
                    state = 'decimal'
                    continue
                
                return False
            
            if state == 'decimal_start':
                if w.isdigit():
                    state = 'decimal'
                    continue
                
                return False
            
            if state == 'decimal':
                if w.isdigit():
                    continue
                
                if w in 'eE':
                    state = 'sign_e'
                    continue
                
                return False
                        
            
            if state == 'sign_e':
                
                if w in '+-':
                    state = 'num_e_start'
                    continue
                
                if w.isdigit():
                    state = 'num_e'
                    continue
                    
                return False
            
            if state == 'num_e_start':
                if w.isdigit():
                    state = 'num_e'
                    continue
                
                return False
            
            if state == 'num_e':
                if w.isdigit():
                    continue
                
                return False
            
        if state == 'integer_start':
            return False
                    
        if state == 'decimal_start':
            return False
        
        if state == 'num_e_start':
            return False
        
        if state == 'sign_e':
            return False
        
        
        return True

Edited on 05/15/2021. Refactor FSM code.

[LeetCode] 64. Minimum Path Sum

Problem : https://leetcode.com/problems/minimum-path-sum/

This problem is similar to 62. Unique Paths

Below implementation uses top-down processing to calculate the minPathSum of the right-bottom position.

Time Complexity :  O ( Row * Column )

Space Complexity : O ( 1 )

from functools import lru_cache

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        @lru_cache(maxsize=None)
        def dfs(i, j):
            if i - 1 >= 0 and j - 1 >= 0:
                return min(dfs(i - 1, j), dfs(i, j - 1)) + grid[i][j]
            
            if i - 1 >= 0:
                return dfs(i - 1, j) + grid[i][j]
            
            if j - 1 >= 0:
                return dfs(i, j - 1) + grid[i][j]
            
            return grid[i][j]
        
        
        row = len(grid)
        column = len(grid[0])
        return dfs(row - 1, column - 1)

The bottom-up solution:

class Solution {
    public int minPathSum(int[][] grid) {
        int ROW = grid.length;
        int COLUMN = grid[0].length;
        
        int[][] dp = new int[ROW][COLUMN];
        
        dp[0][0] = grid[0][0];
        
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COLUMN; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                
                dp[i][j] = grid[i][j] + Math.min(i-1>=0 ? dp[i-1][j] : Integer.MAX_VALUE, j-1>=0 ? dp[i][j-1] : Integer.MAX_VALUE);
            }
        }
        
        return dp[ROW-1][COLUMN-1];
    }
}

Edited on 11/25/2021. Add the bottom-up solution.

[LeetCode] 63. Unique Paths II

Problem :  https://leetcode.com/problems/unique-paths-ii/

Similar to the 62 Unique Paths

Time Complexity : O ( M * N )

Space Complexity : O (M * N )

from functools import lru_cache

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        @lru_cache(maxsize = None)
        def paths(i, j):
            if i < 0 or j < 0:
                return 0
            
            if obstacleGrid[i][j] == 1:
                return 0
            
            # 1 step to start from the top-left cell
            if i == 0 and j == 0:
                return 1
            
            return paths(i-1, j) + paths(i, j-1)
        
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        return paths(m-1, n-1)

A bottom-up DP solution.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        ROW = len(obstacleGrid)
        COLUMN = len(obstacleGrid[0])
        
        dp = [[0] * (COLUMN+1) for _ in range(ROW+1)]
        
        dp[ROW-1][COLUMN-1] = 1 if obstacleGrid[ROW-1][COLUMN-1] != 1 else 0
        
        for y in reversed(range(ROW)):
            for x in reversed(range(COLUMN)):
                if y == ROW-1 and x == COLUMN-1:
                    continue
                    
                if obstacleGrid[y][x] == 1:
                    continue
                
              	
                dp[y][x] = dp[y+1][x] + dp[y][x+1]
                
        return dp[0][0]

Edited on 04/28/2021. Add the DP solution.

[LeetCode] 62. Unique Paths

Problem : https://leetcode.com/problems/unique-paths/

The last step to reach one cell is either from the cell on top or cell on left.

Let paths(i, j) is the unique paths to reach cell (i, j).

paths(i, j) = paths(i-1, j)+ paths(i, j -1).

i is row index which's value range is 1 to M

j is column index which's value range is 1 to N

Use "functools.lru_cache" to cache the intermediate result of the top-down approach.

Time Complexity = O ( M * N ) as the code needs to visit each cell once.

Space Complexity = O ( M * N ) for the memorization cache.

from functools import lru_cache

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        
        @lru_cache(maxsize=None)
        def paths(i, j):
            if j <= 0 or i <= 0:
                return 0
            
            # 1 step to start from the top-left cell
            if i == 1 and j == 1:
                return 1
            
            return paths(i, j-1) + paths(i-1, j)
        
        return paths(m, n)

[LeetCode] 61. Rotate List

Problem : https://leetcode.com/problems/rotate-list/

Step 1.  Link the tail and head element to make a circuit linked list.

Step 2.  Rotate the list to right by k places equal to move head to position Total - k % Total 

Step 3.  Move to the new head and break the circuit linked list

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        
        if not head:
            return None
        
        p = head
        total = 1
        
        while p.next:
            total += 1
            p = p.next
        
        # link th tail and head
        p.next = head
        
        # find the new head position
        k = total - (k % total) - 1
        
        p = head
        while k > 0:
            p = p.next
            k -= 1
        
        head = p.next
        p.next = None
        
        
        return head

[LeetCode] 60. Permutation Sequence

Problem : https://leetcode.com/problems/permutation-sequence/

When N = 3, we have below sequences : 

[1]  1 2 3

[2]  1 3 2

[3]  2 1 3

[4]  2 3 1

[5]  3 1 2

[6]  3 2 1

Initially,

Nums =  [1, 2, 3]

Total sequences are 3! =  3 * 2 * 1

There are 3 main groups.  In each group it is the full permutation of the rest numbers.

The first number of 3rd sequence =  (3 - 1) // 6 // 3 = 1.  Nums[1] == 2.  So the first number is 2.

Take 2 from the number array,

Nums = [1, 3]

Total sequences are 2! = 2 * 1

Now we need to locate the  (3-1) % 2 + 1 = 1, the 1st sequence of [1,3]'s full permutation.

There are 2 main groups. In each group it is the full permutation of the rest numbers.

So the first number of 1st sequence =  (1-1) // 2 // 1  = 0.  Nums[0] =  1. So the second number is 3.

Take 3 from the number array,

Nums = [1]

Total sequences is 1! = 1

Now we need to locate the (1 - 1) % 1 + 1 = 1, the 1st sequnce of [1]'s full permutation.

So the first number of 1st sequence = (1 - 1) // 1 // 1 =  0. Nums[0] = 1. So the thrid number is 1.

Time Complexity = O ( N )

Space Complexity =  O ( 1 ) 

from operator import imul

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        
        nums = [str(i) for i in range(1, n+1)]
        
        # total = n!
        total = reduce(imul, range(1,n+1))
        result = ""
        
        k -= 1  # number index starts from 0
        
        while n > 0:
            group = total // n
            
            i = k // group
            
            result += nums[i]
            nums.pop(i)
            
            k = k % group 
            
            total = total // n
            n -= 1
            
        return result

[LeetCode] 59. Spiral Matrix II

Problem : https://leetcode.com/problems/spiral-matrix-ii/

Use FSM to simulate the process for filling numbers. Be careful, it must break the loop immediately when i >= n * n.

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        
        board = [[0] * n for _ in range(n)]
        
        i = 1
        board[0][0] = 1
        
        y, x = 0, 0
        padding_y, padding_x = 0, 0
        
        state = 'right'
        
        while True:
            if state == 'right':
                if x + 1 >= n - padding_x:
                    state = 'down'
                else:
                    x += 1
                    i += 1
                    board[y][x] = i
            
            elif state == 'down':
                if y + 1 >= n - padding_y:
                    state = 'left'
                else:
                    y += 1
                    i += 1
                    board[y][x] = i
                    
            elif state == 'left':
                if x - 1 < padding_x:
                    state = 'up'
                    padding_y += 1
                else:
                    x -= 1
                    i += 1
                    board[y][x] = i
                    
            elif state == 'up':
                if y - 1 < padding_y:
                    state = 'right'
                    padding_x +=1 
                else:
                    y -= 1
                    i += 1
                    board[y][x] = i
                    
            if i >= n * n:
                break
                    
        return board

[LeetCode] 58. Length of Last Word

Problem : https://leetcode.com/problems/length-of-last-word/

It looks easy but need to consider the case that there are white spaces on the end of string.

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        result = 0
        for i in reversed(range(len(s))):
            if s[i] == ' '  and result > 0:
                break

            if s[i] != ' ':
                result += 1
        
        return result

[LeetCode] 57. Insert Interval

Problem : https://leetcode.com/problems/insert-interval/

Consider the new interval as a single item list. Since the original intervals are sorted, use merging sort alike process to merge the 2 lists.

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        Deque<int[]> result = new LinkedList<>();

        boolean added = false;
        int i = 0;

        while (i <= intervals.length) {
            int[] next;

            if (i < intervals.length && (added || intervals[i][0] <= newInterval[0])) {
                next = intervals[i];
                i += 1;
            } else if (!added) {
                next = newInterval;
                added = true;
            } else {
                break;
            }

            if (result.peekLast() == null || result.peekLast()[1] < next[0]) {
                result.offerLast(next);
            } else {
                result.peekLast()[0] = Math.min(result.peekLast()[0], next[0]);
                result.peekLast()[1] = Math.max(result.peekLast()[1], next[1]);
            }
        }

        return result.toArray(new int[0][0]);
    }
}

Binary search based solution:

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        newStart, newEnd = newInterval
        
        # find the lower bound insertion position
        left, right = 0, len(intervals)
        while left < right:
            mid = left + (right - left) // 2
            
            start, end = intervals[mid]
            
            if start <= newStart <= newEnd <= end:
                return intervals
            
            if start < newStart:
                left = mid + 1
            elif start > newStart:
                right = mid
            else: # start == newStart
                right = mid
        
        if left == len(intervals):
            intervals.append(newInterval)
        
        intervals.insert(left, newInterval)
        
        # merge intervals
        i = j = left - 1 if left - 1 >= 0 else 0
        
        while j < len(intervals):
            if intervals[i][0] <= intervals[j][0] <= intervals[i][1]:
                intervals[i][0] = min(intervals[i][0], intervals[j][0])
                intervals[i][1] = max(intervals[i][1], intervals[j][1])
            else:
                i += 1
                intervals[i][0] = intervals[j][0]
                intervals[i][1] = intervals[j][1]
                
            j += 1
       
        return intervals[:i+1]

Updated on 01/15/2023. Updated the linear scan approach with a concise implementation.

[LeetCode] 56. Merge Intervals

Problem : https://leetcode.com/problems/merge-intervals/

Sort intervals by its start point first.  The iterate the interval list and merge intervals overlaps.

from operator import itemgetter
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    
        intervals.sort()
        
        result = []

        for start, end in intervals:
            if result and result[-1][0] <= start <= result[-1][1]:
                result[-1][0] = min(result[-1][0], start)
                result[-1][1] = max(result[-1][1], end)
            else:
                result.append([start, end])
        
        
        return result

[LeetCode] 55. Jump Game

Problem : https://leetcode.com/problems/jump-game/

A typical greedy algorithm problem. Iterate the input array and locate the furthest position can be reached.

Time Complexity : O ( N )

Space Complexity : O ( 1 )

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        N = len(nums)
        maxSoFar = 0
        
        for i, n in enumerate(nums):
            if maxSoFar >= N - 1:
                return True
            
            if i > maxSoFar:
                return False
            
            if i + nums[i] > maxSoFar:
                maxSoFar = i + nums[i]
        
        
        return False

A memorization solution:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        N = len(nums)
        
        @cache
        def helper(x):
            if x >= N-1: return True
            return any(helper(x + s) for s in reversed(range(1, nums[x] + 1)))

        return helper(0)

[LeetCode] 54. Spiral Matrix

Problem : https://leetcode.com/problems/spiral-matrix/

Use FSM to simulate the process of iterating element and put the visited element to result array.

Stop iterating when result array size equals to the matrix size. 

Remember to handle the edge case when input matrix is empty.

Time Complexity : O ( M * N )

Space Complexity: O ( M * N )

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        nextPos = {'right': (0, 1), 'down': (1, 0), 'left': (0, -1), 'up': (-1, 0)}
        nextDir = {'right': 'down', 'down': 'left', 'left': 'up', 'up': 'right'}
        
        y, x = 0, -1
        direction = 'right'
        
        result = []
        visited = defaultdict(bool)
        
        while len(result) < ROW * COLUMN:
            ny, nx = y + nextPos[direction][0], x + nextPos[direction][1]
            
            if 0 <= ny < ROW and 0 <= nx < COLUMN and not visited[ny,nx]:
                visited[ny, nx] = True
                result.append(matrix[ny][nx])
                y, x = ny, nx
            else:
                direction = nextDir[direction]
            
        return result

Edited on 09/16/2021. Refactor by using dictionary to save next position to move forward and next direction when need to make a turn.

[LeetCode] 53. Maximum Subarray

Problem : https://leetcode.com/problems/maximum-subarray/

O( N ) time complexity solution is based on DP.

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
    
        result = -2 ** 31
        tmp = 0
        
        for i in range(len(nums)):
            # restart sub-array from i if its sum less than nums[i]
            tmp = max(tmp + nums[i], nums[i])            
            result = max(result, tmp)

        return result

Divide and conquer solution:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        def helper(start, end):
            if end - start == 1:
                return nums[start]
            
            mid = start + (end - start) // 2
            
            # max of left sub-array
            left_max = helper(start, mid)
            
            # max of right sub-array
            right_max = helper(mid, end)
        
            # max of middle
            mid_max = nums[mid]
            t = mid_max
            
            for i in range(mid-1, start-1, -1):
                t += nums[i]
                mid_max = max(mid_max, t)
                
            t = mid_max
            for i in range(mid+1, end): 
                t += nums[i]
                mid_max = max(mid_max, t)
            
            return max(left_max, mid_max, right_max)
            
         
        return helper(0, len(nums))
    

[LeetCode] 52. N-Queens II

Problem : https://leetcode.com/problems/n-queens-ii/

Same to the 51. N-Queens

class Solution:
    def totalNQueens(self, n: int) -> int:
        
        @cache
        def getOccupies(y, x):
            occupies = [(y, x)]
            for dy, dx in [(1,0), (0,1), (1,1), (1,-1)]:
                tmpY, tmpX = y+dy, x+dx
                
                while 0 <= tmpY < n and 0 <= tmpX < n:
                    occupies.append((tmpY, tmpX))
                    tmpY += dy
                    tmpX += dx
            
            return occupies
        
        
        def backtrack(y, board):
            if y == n:
                yield 1
            else:
                for x in range(n):
                    if board[y][x]:
                        # skip this position as it has been occupied
                        continue
                    
                    myOccupies = getOccupies(y,x)
                    
                    for py, px in myOccupies:
                        board[py][px] += 1
                    
                    yield from backtrack(y+1, board)
                    
                    for py, px in myOccupies:
                        board[py][px] -= 1
        
        board = [[0] * n for _ in range(n)]
        return sum(backtrack(0, board))

Edited on 05/22/2021. Use memorization to simplify the code for checking whether one position is valid to put a Queen.

Edited on 05/29/2021. Optimize performance by only marking positions on right and on rows below.

[LeetCode] 51. N-Queens

Problem : https://leetcode.com/problems/n-queens/

A typical backtracking problem. Simulate the process to check if it is valid to put queen on current position. Otherwise, return to the last state.

 

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        board = [[0] * n for _ in range(n)]
        result = []
        
        def toBoard(queens):
            return [''.join(['Q' if x == queens[y] else '.' for x in range(n)]) for y in range(n)]
        
        @cache
        def getOccupied(y, x):
            occupied = [(y,x)]
            
            # because we scan from left to right and top to bottom
            # it only needs to mark the poisition on right and on rows below
            for dy, dx in [(1,0), (0,1), (1, 1), (1, -1)]:
                tmpY, tmpX = y + dy, x + dx
                while 0 <= tmpY < n and 0 <= tmpX < n:
                    occupied.append((tmpY, tmpX))
                    tmpY += dy
                    tmpX += dx
                
            return occupied
        
        def backtrack(y, queens):
            if y == n:
                yield toBoard(queens)
            else:
                for x in range(n):
                    if board[y][x]:
                        continue
                    
                    myOccupied = getOccupied(y, x)
                    
                    for occupiedY, occupiedX in myOccupied:
                        board[occupiedY][occupiedX] += 1
                        
                    queens.append(x)
                    yield from backtrack(y+1, queens)
                    queens.pop()
                    
                    for occupiedY, occupiedX in myOccupied:
                        board[occupiedY][occupiedX] -= 1
        
        return list(backtrack(0, []))

Edited on 05/22/2021. Simplify the method for caculating occupied positions.

Edited on 05/29/2021. Optimize performance by only marking poisition on right and on rows below.

[LeetCode] 50. Pow(x, n)

Problem : https://leetcode.com/problems/powx-n/description/

Use memorization to save result from previous calculation

Time Complexity :  O( Log(n) )

class Solution(object):
    class Solution:
    def myPow(self, x: float, n: int) -> float:
        
        @lru_cache(maxsize = None)
        def helper(i):
            if i == 0:
                return 1
            
            if i == 1:
                return x
            
            return helper(i//2) * helper(i//2) * helper(i % 2)
        
        return helper(n) if n >= 0 else 1 / helper(-1 * n)

Another recursive solution:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1

        if n == 1:
            return x
        
        positive = True
        
        if n < 0:
            positive = False
            n *= -1
            
        result = self.myPow(x, n // 2)
        result *= result
        
        if n % 2:
            result *= x
        
        return result if positive else 1 / result

[LeetCode] 49. Group Anagrams

Problem : https://leetcode.com/problems/group-anagrams/description/

Sort string to calculate the key of this string.

Time Complexity : O( N * K * Log(K) ).   N is number of strings. K is maximum length of string.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        seen = defaultdict(list)
        
        for s in strs:
            seen[tuple(sorted(s))].append(s)
        
        return seen.values()

[LeetCode] 48. Rotate Image

Problem : https://leetcode.com/problems/rotate-image/description/

Use common method to rotate matrix in clockwise.

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        
        # reverse  rows
        left, right = 0, len(matrix)-1
        while left <= right:
            matrix[left], matrix[right] = matrix[right], matrix[left]
            left += 1
            right -= 1
                                                             
        
        # swap the symmetry
        
        for i in range(len(matrix)):
            for j in range(i+1, len(matrix[i])):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]       

Rotate matrix in anticlockwise:

# reverse each row
for i in range(len(maxtrix)):
	reverse(matrix[i])
    
# swap the symmetry
for i in range(len(matrix)):
	for j in range(i+1, len(matrix[i])):
		matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]       

[LeetCode] 47. Permutations II

Problem : https://leetcode.com/problems/permutations-ii/description/

This problem is similar to 46. Permutations

To avoid duplication, the input array needs to be sorted first.

So we avoid picking number with same value as the start number of permutation.

Instead of swapping numbers, we need to take out the selected number to keep the sorted order of original array.

Time Complexity = O(N * N!)

Space Complexity = O(N * N!)

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # sort to group number with same value together
        nums.sort()
        result = []
        
        def backtrack(tmp):
            if not nums:
            	# no more candidate number left
                if tmp:
                    result.append(partial)
                return
            
            for i in range(0, len(nums)):
                # skip number with same value to avoid duplicatation
                if i > 0 and nums[i] == nums[i-1]:
                    continue
                
                # take the selected number out of candidate array
                n = nums.pop(i)
                
                backtrack(tmp + [n])
                
                # restore candidate array
                nums.insert(i, n)
                
        backtrack([])
        return result

Use hash table to avoid duplicate permutation

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def backtrack(start):
            if start == len(nums):
                result.append(nums[:])
            else:
                seen = set()
                for i in range(start, len(nums)):
                    if nums[i] in seen:
                        continue
                    
                    seen.add(nums[i])
                    
                    nums[start], nums[i] = nums[i], nums[start]
                    backtrack(start + 1)
                    nums[start], nums[i] = nums[i], nums[start]
        
        backtrack(0)
        return result

A hash table backed backtracking approach.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        counter = Counter(nums)
        keys = counter.keys()
        
        def backtrack(tmp):
            if len(tmp) == len(nums):
                result.append(tmp)
            else:
                for k in keys:
                    if counter[k] == 0:
                        continue
                        
                    counter[k] -= 1
                    backtrack(tmp + [k])
                    counter[k] += 1
        
        backtrack([])
        return result

[LeetCode] 46. Permutations

Problem : https://leetcode.com/problems/permutations/description/

Use backtracking approach to find all combinations.

Let permutation[i] = permutation starts with nums[i],

nums[] - nums[i] = nums without nums[i]

permutation[i] = nums[i] + permutation( nums[] - nums[i] )

Time Complexity = O(n * n!)

Space Complexity = O(n * n!)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        if not nums: return []
        
        N = len(nums)
        result = []
        
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]
        
        def backtrack(start):
            if start == N:
                result.append(nums[:])
            else:
                for i in range(start, N):
                    swap(i, start)
                    backtrack(start+1)
                    swap(i, start)
        
        backtrack(0)
        return result

[LeetCode] 45. Jump Game II

problem : https://leetcode.com/problems/jump-game-ii/description/

DP Solution:

DP[i] = the minimal steps needed to reach position i

Time Complexity = O(N * Max(Nums[i]))

class Solution:
    def jump(self, nums: List[int]) -> int:
        max_int = 2 ** 31 - 1
        
        dp = [max_int] * len(nums)
        dp[0] = 0
        
        for i in range(len(nums)):
            # The furthest postion can be reached
            # from index i is nums[i+nums[i]].
            #
            # However, there is routine with less step 
            # to reach to nums[i+nums[i]].
            #
            # So including nums[i] in routine does not
            # decrease the total steps
            if i + nums[i] < len(nums) and dp[i] + 1 >= dp[i + nums[i]]:
                continue
                
            for j in range(1, nums[i]+1):
                if i + j >= len(nums) - 1:
                    dp[-1] = min(dp[-1], dp[i] + 1)
                else:
                    dp[i+j] = min(dp[i+j], dp[i]+1)
        
        return dp[-1]

Greedy Solution:

Time Complexity = O ( N )

class Solution:
    def jump(self, nums: List[int]) -> int:
        result = 0
        last_furthest = 0
        furthest = 0
        
        for i in range(0, len(nums) - 1):
            # Extend the furthest position can be reached
            if furthest >= i and nums[i] + i > furthest:
                furthest = nums[i] + i
            
            # If current position equals to the last furthest position
            # can be reached or it equals to the end of list, increase step counter. 
            # As it needs one more step to reach to the current furthest position.
            if i == last_furthest or furthest >= len(nums) - 1:
                last_furthest = furthest
                result += 1
            
            if furthest >= len(nums) - 1:
                break
        
        return result      

[LeetCode] 44. Wildcard Matching

Problem : https://leetcode.com/problems/wildcard-matching/

This problem is similar to  10. Regular Expression Matching

It is a simple problem if we don't consider character '*'. 

When it encounters '*',  it has 2 options:

1. Use '*' to match the current character in S and keep the '*' for the next character matching
2. Skip '*' as  '*' is used to match empty sequence. Then use next character in P to match current character in S.

To avoid checking if S[i] matches P[j] repeatedly, it needs to memorize the result from previous iteration.

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        
        memo = [[0] * (len(p)+1) for _ in range(len(s)+1)]
        
        def helper(i, j):
            if j >= len(p):
                return i >= len(s)
            
            if memo[i][j] != 0:
                return memo[i][j] == 1
            
            if i < len(s) and s[i] == p[j]:
                return helper(i+1, j+1)
            
            if i < len(s) and p[j] == '?':
                return helper(i+1, j+1)
            
            if i < len(s) and p[j] == '*':
            
            	# Match S[i] with '*'
                # Move to next character of S
                # Keep '*' in P
                if helper(i+1, j):
                    memo[i][j] = 1
                    return True
            	
                # Use '*' to match empty sequence
                # Stay on the current character of S
                # Move to next character of P 
                if helper(i, j+1):
                    memo[i][j] = 1
                    return True
            
            if i == len(s) and p[j] == '*':
                return helper(i, j+1)
            
            memo[i][j] = -1
            return False
                
        return helper(0, 0)

[LeetCode] 43. Multiply Strings

Problem : https://leetcode.com/problems/multiply-strings/

Simulate the process of multiplying 2 numbers.

Time Complexity = O( len(nums1) * len(nums2) )

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
    
        def mul(a, b):
            result = []
            carry = 0
            
            for n in a[::-1]:
                t = n * b + carry
                result.append(t%10)
                carry = t // 10
            
            if carry:
                result.append(carry)
            
            return result[::-1]
            
        def plus(a, b):
            
            i, j = len(a)-1, len(b)-1
            carry = 0
            result = []
            
            while i >= 0 or j >= 0 or carry:
                t = carry
                if i >= 0:
                    t += a[i]
                if j >= 0:
                    t += b[j]
                result.append(t%10)
                carry = t // 10
                
                i -= 1
                j -= 1
            
            return result[::-1]
            
        
        num1 = [int(n) for n in num1]
        num2 = [int(n) for n in num2]
        
        base = 0
        tmp = []
        
        for n in num2[::-1]:
            t = mul(num1, n)
            for i in range(base):
                t.append(0)
            
            tmp.append(t)
            base += 1
        
        result = [0]
        
        for i in range(len(tmp)):
            result = plus(tmp[i], result)
        
        return ''.join(map(str,result)) if result[0] != 0 else '0'

Edited on 11/07/2021. Tidy the solution.

[LeetCode] 42. Trapping Rain Water

Problem : https://leetcode.com/problems/trapping-rain-water/

It is intuitive that if one position can contain water, it must be on the lower level of both left and right side.

So we may iterate from left to right to find the maximum height of each bar from left.

Then iterate from right to left to find the maximum height of each bar from right.

The volume of each bar  = Min( maximum_height_from left,  maximum_height_from_right ) - bar_height.

Time Complexity = O ( N + N + N )

class Solution:
    def trap(self, height: List[int]) -> int:
        N = len(height)
        if N < 2: return 0
        
        # left[i] = maximum height from left of position i
        left = [0] * N
        mx = 0
        for i in range(N):
            left[i] = mx
            mx = max(mx, height[i])
        
        # right[i] = maximum height from right of position i
        right = [0] * N
        mx = 0
        for i in reversed(range(N)):
            right[i] = mx
            mx = max(mx, height[i])
        
        result = 0
        for i in range(N):
            # maximum water can be contained at ith position
            result += max(0, min(left[i], right[i]) - height[i])
        
        return result

Monotonic stack based solution. Time Complexity = O ( 2 * N ), because for every position it could be visited at most 2 times. 

class Solution:
    def trap(self, height: List[int]) -> int:
        
        # maintain a monotonic decreasing stack 
        stack = []
        result = 0
        
        for right in range(len(height)):
            
            # it can form a cavity if we find a taller right bar
            while stack and height[stack[-1]] < height[right]:
                bottom = stack.pop()
                
                # break if cannot find left bar
                if not stack:
                    break
                    
                left = stack[-1]
                
                # calculate the portion of water can be contained by this position
                bound_distance = right - left - 1
                bound_height = min(height[left], height[right]) - height[bottom]
                
                result += bound_distance * bound_height
                
            stack.append(right)
         
        return result

Edited on 06/18/2021. Update a more intuitive solution.

Edited on 08/01/2021. Add the monotonic stack based solution.

[LeetCode] 41. First Missing Positive

Problem : https://leetcode.com/problems/first-missing-positive/

Positive numbers start from 1. 

Solution 1: 

Use hash set to record all the exiting numbers. Then iterate from 1 and return the first number not in hash set.

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        memo = set(nums)
        
        i = 1
        while i in memo:
            i += 1
        
        return i

Solution 2:

In perfect case, the array contains the contiguous numbers starts from 1.

Such as:  [1, 2, 3, 4, 5, ...]

As it shows,  nums[i]  - 1 == i

Use the array-index to record existing numbers.

For all existing number,  nums[ nums[i] - 1 ]  == nums[i].

The missing number is the first item which nums[i] != i + 1

Time complexity = O ( 2 * N )

Space complexity = O ( N )

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        for i in range(len(nums)):
            while nums[i] > 0 and nums[i] <= len(nums) and nums[nums[i]-1] != nums[i]:
                # swap nums[i] and nums[nums[i] -1]
                # must save nums[i] with tmp
                # because current value of nums[i] 
                # will be used to calculate index
                tmp = nums[i]  
                nums[i] = nums[nums[i]-1]
                nums[tmp-1] = tmp
                
        
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        
        return len(nums) + 1

[LeetCode] 40. Combination Sum II

Problem :  https://leetcode.com/problems/combination-sum-ii/

Should sort the candidates array first and skip candidate which has same value as its previous one to avoid duplicate result

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        result = []
        L = len(candidates)
        candidates.sort()
        
        def backtracking(start, partial, n):
            if n == 0:
                if partial:
                    result.append(partial)
                    
            for i in range(start, L):
                if n - candidates[i] < 0:
                    break
                
                # skip candidates with same value to avoid duplicate result
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                
                backtracking(i + 1, partial + [candidates[i]], n - candidates[i])
            
        backtracking(0, [], target)
        
        return result

[LeetCode] 39. Combination Sum

Problem : https://leetcode.com/problems/combination-sum/

Backtracking based solution:

Consider the code is travelling a tree. On each tree node, the code has len(candidates) options to choose to move to the next node. The traversal ends when sum of the collected nodes value equal to the target number.

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        N = len(candidates)
        result = []
        
        def backtracking(start, partial, n):
            if n == 0:
                if partial:
                    result.append(partial)
                return
            
            for i in range(start, N):
                if n - candidates[i] >= 0:
                    backtracking(i, partial + [candidates[i]], n - candidates[i])
                else:
                    # since the rest of candiates are larger than current one
                    # it can safely terminate here.
                    break
        
        # sort the candidates first for faster searching.
        candidates.sort()
        backtracking(0, [], target)
        
        return result

Another backtracking based solution:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        
        for i in range(len(candidates)):
            n = candidates[i]
            if n == target:
                result.append([n])
            elif n < target:
                # [n] + combinations of numbers sum to (target - n)
                # use candidates[i:] to avoid duplicate combo
                for combo in self.combinationSum(candidates[i:], target - n):
                    result.append([n] + combo)
        
        return result

Memorization based solution:

Let A + B = C and Helper(B) = all combinations which sum to target B.

Helper (C) =  [A] combines with each combination returned by Helper(B)

The candidates need to be sorted first to avoid duplicate combination.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        candidates.sort()
        
        @lru_cache(maxsize = None)
        def helper(target):
            result = []
            
            # candidates is array of distinct integers
            # it is safe to iterate each number 
            for n in candidates:
                if n == target:
                    result.append([n])
                elif n < target:
                    for combo in helper(target - n):
                        # to avoid duplicate result,
                        # only combine when the first number is larger or equal to n
                        if n <= combo[0]:
                            result.append([n] + combo)
            
            return result
        
        return helper(target)

The bottom-up solution:

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        HashMap<Integer, List<List<Integer>>> memo = new HashMap();
        
        List<List<Integer>> emptyList = new ArrayList();
        emptyList.add(new ArrayList<Integer>());
        
        memo.put(0, emptyList);
        
        for (int n : candidates) {
            for (int t = n; t <= target; t++) {
                if (!memo.containsKey(t-n)) {
                    continue;
                }
                
                if (!memo.containsKey(t)) {
                    memo.put(t, new ArrayList<List<Integer>>());
                }
         
                for (List<Integer> prefix : memo.get(t-n)) {
                    List<Integer> tmp = new ArrayList();
                    tmp.addAll(prefix);
                    tmp.add(n);
                    
                    memo.get(t).add(tmp);
                }
            }
        }
        
        return memo.getOrDefault(target, new ArrayList<List<Integer>>());
    }
}

Edited on 12/02/2021. Add the bottom-up solution.

[LeetCode] 38. Count and Say

Problem : https://leetcode.com/problems/count-and-say/

To generate the Nth term, just count and say the (N-1)th term

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        
        if n == 1:
            return "1"
        
        result = ""
        stack = []
      
        for w in self.countAndSay(n-1):
            if not stack or stack[-1] == w:
                stack.append(w)
            else:
                result += str(len(stack)) + stack[-1]
                stack = [w]

        if stack:
            result += str(len(stack)) + stack[-1]
        
        return result

[LeetCode] 37. Sudoku Solver

Problem :  https://leetcode.com/problems/sudoku-solver/

Simulate the process to fill the empty cell with number 1 to 9, then validate whether it is a valid filling. If the number is valid, move the next empty cell. Otherwise back to the last cell and try another number.

Because all the previous filled numbers have been verified, it only needs to validate the number of current cell.

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        ROW = 9
        COLUMN = 9
        
        rowMask = [0] * 9
        columnMask = [0] * 9
        subboxMask = [0] * 9
        
        
        for y in range(ROW):
            for x in range(COLUMN):
                if board[y][x] != '.':
                    n = int(board[y][x])

                    rowMask[y] |= (1 << n)
                    columnMask[x] |= (1 << n)
                    
                    subboxMask[3*(y//3) + x//3] |= (1<<n)
        
        
        def helper(y, x):
            if y >= ROW:
                return True
            
            nx = x + 1
            ny = y
            
            if nx >= COLUMN:
                nx = 0
                ny += 1
            
            if board[y][x] != '.':
                return helper(ny, nx)
            else:
                for i in range(1, 10):
                    if rowMask[y] & (1 << i):
                        continue
                    
                    if columnMask[x] & (1 << i):
                        continue
                    
                    if subboxMask[3*(y//3) + x//3] & (1 << i):
                        continue
                    
                    board[y][x] = str(i)
                    rowMask[y] |= (1 << i)
                    columnMask[x] |= (1 << i)
                    subboxMask[3*(y//3) + x//3] |= (1 << i)
                    
                    if helper(ny, nx):
                        return True
                    
                    board[y][x] = '.'
                    rowMask[y] ^= (1 << i)
                    columnMask[x] ^= (1 << i)
                    subboxMask[3*(y//3) + x//3] ^= (1 << i)
                
                return False
        
        helper(0,0)

Edited on 08/21/2021. Use bitmask to improve performance.

[LeetCode] 36. Valid Sudoku

Problem : https://leetcode.com/problems/valid-sudoku/

Simulate the process to valid sudoku map

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        ROW = COLUMN = 9
        
        def verifyRows():
            for y in range(ROW):
                seen = set()
                for x in range(COLUMN):
                    if board[y][x] == '.':
                        continue
                        
                    if board[y][x] in seen:
                        return False
                    
                    seen.add(board[y][x])
            return True
        
        def verifyColumns():
            for x in range(COLUMN):
                seen = set()
                for y in range(ROW):
                    if board[y][x] == '.':
                        continue
                    
                    if board[y][x] in seen:
                        return False
                    
                    seen.add(board[y][x])
            return True
        
        def verifySubBoxs():
            for sy in range(0, ROW, 3):
                for sx in range(0, COLUMN, 3):
                    seen = set()
                    for y in range(sy, sy+3):
                        for x in range(sx, sx+3):
                            if board[y][x] == '.':
                                continue

                            if board[y][x] in seen:
                                return False

                            seen.add(board[y][x])
            return True
       
        return verifyRows() and verifyColumns() and verifySubBoxs()

Edited on 08/20/2021. Tidy the solution.

[LeetCode] 35. Search Insert Position

Problem :  https://leetcode.com/problems/search-insert-position/

Time Complexity : O( Log( len(nums ) ) )

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0; int right = nums.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

Edited on 11/25/2021. Update the Java solution.

[LeetCode] 34. Find First and Last Position of Element in Sorted Array

Problem : https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Search the left most element and right most element separately.

Push the "right' pointer to left as far as possible to find the left most element.

Push the "left" pointer to right as far as possible to find the right most element.

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        def leftMost(left, right):
            while left < right:
                mid = left + (right - left) // 2
                
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid   # push 'right' to left as far as possible
            
            if right < len(nums) and nums[right] == target:
                return right
            
            return -1
        
        def rightMost(left, right):
            while left < right:
                mid = left + (right - left) // 2
                
                if nums[mid] <= target:
                    left = mid + 1  # push 'left' to right as far as possible
                else:
                    right = mid
                
            return left - 1
     
        left = leftMost(0, len(nums))
        if left == -1:
            return [-1, -1]
        
        return [left, rightMost(left, len(nums))]

Use built-in function:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = bisect.bisect_left(nums, target)
        if left == len(nums) or nums[left] != target:
            return -1, -1
        
        right = bisect.bisect_right(nums, target) - 1
        
        return left, right

Edited on 02/27/2021. Use buillt-in lib.

[LeetCode] 33. Search in Rotated Sorted Array

Problem : https://leetcode.com/problems/search-in-rotated-sorted-array/

Array [ 0, 1,  2,  4,  5,  6, 7 ] can generate below rotated arrays:

0　　1　　2　　 4　　5　　6　　7

7　　0　　1　　 2　　4　　5　　6

6　　7　　0　　 1　　2　　4　　5

5　　6　　7　　 0　　1　　2　　4

4　　5　　6　　7　　0　　1　　2

2　　4　　5　　6　　7　　0　　1

1　　2　　4　　5　　6　　7　　0

Base on the sample data,  it shows that when nums[mid] < nums[right],  the right part is sorted.  Otherwise, the left part is sorted. So we may use the "First" and "Last" number of the sorted part to decide search in left of right part.

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return mid
            
            if nums[mid] < nums[right]:
                # right part is sorted
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                # left part is sorted
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid +1
                    
        return -1

[LeetCode] 32. Longest Valid Parentheses

Problem : https://leetcode.com/problems/longest-valid-parentheses/

Consider DP[i] = the longest valid parentheses ends with s[i].

To make a valid parentheses pair, s[i] must be ')'.

When S[i-1] = '(':      # ****()

    DP[i] = DP[i-1] + 2

When S[i-1] = ')'  And S[i - DP[i-1] - 1] == '(':    # ***((***))

    DP[i] = DP[i- DP[i-1] - 2] + DP[i-1] + 2

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0
        
        N = len(s)
        dp = [0] * N
        
        for i in range(1, N):
            if s[i] == '(':
                continue
            
            # s[i] == ')'
            if s[i-1] == '(':
                dp[i] = dp[i-2] + 2
            else:
                left = i - dp[i-1] - 1
                
                if left >= 0 and s[left] == '(':
                    dp[i] = dp[i-1] + 2
                    
                    if left - 1 >= 0:
                        dp[i] += dp[left - 1]
            
        return max(dp)

A Top-Down approach:

class Solution:
    def longestValidParentheses(self, s: str) -> int:

        @lru_cache(maxsize = None)
        def helper(i):
            if i <= 0 or s[i] == '(': return 0
            
            # s[i] == ')'            
            if i - 1 >= 0:
                if s[i-1] == '(':
                    return helper(i-2) + 2
                else:
                    # s[i-1] == ')'
                    n = helper(i-1)
                    
                    if n > 0:
                        left = i - n - 1
                        if left >= 0 and s[left] == '(':
                            return helper(left-1) + 2 + helper(i-1)
            
            return 0
        
        N = len(s)
        return max(map(helper, range(N))) if N > 0 else 0

Edit on 04/03/2021. Add the Top-Down approach.

[LeetCode] 31. Next Permutation

Problem : https://leetcode.com/problems/next-permutation/

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        def reverse(nums, start, end):
            left = start
            right = end - 1

            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        if len(nums) < 2:
            return nums

        i = len(nums) - 2

        # find pivot which is the first number from back where acending order starts 
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1

        if i == -1:
            nums.sort()
            return nums

        # find the first number from back which is just larger than the pivot number
        j = len(nums) - 1
        while j > i and nums[j] <= nums[i]:
            j -= 1

        # swap
        nums[i], nums[j] = nums[j], nums[i]

        # reverse the right of pivot
        reverse(nums, i+1, len(nums))
        return nums

[LeetCode] 30. Substring with Concatenation of All Words

Problem : https://leetcode.com/problems/substring-with-concatenation-of-all-words/

Because all the words are with same length.  Assume word length is N, the code pickup every substring of length N to check if the substring is in the words array.

Time Complexity : O ( Len(s) *  Len(words) )

Space Complexity:  O ( N )

from collections import defaultdict

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        
        result = []
        
        if not s or not words:
            return result
        
        L = len(words)
        N = len(words[0])
        
        wordCnt = defaultdict(int)
        for w in words:
            wordCnt[w] += 1
            
       
        for i in range(len(s) - N*L + 1):
            # counter of a valid word in range [i : i+N*L+1]
            strCnt = defaultdict(int)
            
            for j in range(L):
                substr = s[i+j*N: i+j*N+N]
                
                if wordCnt[substr] == 0:
                    break
                    
                strCnt[substr] += 1
                
                if strCnt[substr] > wordCnt[substr]:
                    break
            else:
                result.append(i)
                
        return result

[LeetCode] 29. Divide Two Integers

Problem : https://leetcode.com/problems/divide-two-integers/

Dividend / Divisor = Quotient + Remainder 

Quotient means how many 'Divisor' can be found in range of [0, Dividend]

Time Complexity :  O ( Log ( dividend ) )

Space Complexity : O ( 1 )

MAX_INT = 2 ** 31 - 1
MIN_INT = -2 ** 31
    
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0: return 0
        
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        
        if dividend == MIN_INT:
            if divisor == MIN_INT: return 1
            if divisor == -1: return MAX_INT
            
            divisor = abs(divisor)
            
            return sign * (1 + self.divide(abs(dividend + divisor), divisor))
        
        if divisor == MIN_INT: return 0
        
        if abs(divisor) == 1: return sign * abs(dividend)
        
        dividend = abs(dividend)
        divisor = abs(divisor)
        
        result = 0
        
        while divisor <= dividend:
            tmp = divisor
            count = 1
            while tmp << 1 <= dividend:
                count <<= 1
                tmp <<= 1
            
            dividend -= tmp
            result += count
        
        return sign * result

Edited on 02/27/2021. Process edge case when dividend == MIN_INT.

[LeetCode] 28. Implement strStr()

Problem : https://leetcode.com/problems/implement-strstr/

This is a pretty naive approach.

Time Complexity :  O (len(haystack) * len(needle) )

Space Complexity:  O ( 1 )

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        
        if not needle:
            return 0
        
        for i in range(len(haystack) - len(needle) + 1):
            for j in range(len(needle)):
                if haystack[i+j] != needle[j]:
                    break
            else:
                # for-loop completed without break
                return i
        
        return -1

[LeetCode] 27. Remove Element

Problem : https://leetcode.com/problems/remove-element/

Use 2 pointers approach.

Time Complexity :  O ( N )

Space Complexity : O ( 1 )

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        
        p1, p2 = 0, 0
        
        while p2 < len(nums):
            if nums[p2] != val:
                nums[p1] = nums[p2]
                p1 += 1
            
            p2 += 1
            
        return p1

[LeetCode] 26. Remove Duplicates from Sorted Array

Problem : https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Use 2 pointers to traverse the sorted array. p2 moves forward 1 number each time. p1 moves forward only when find unique number.

Time Complexity :  O ( len(nums) )

Space Complexity:  O ( 1 ),   remove duplicated number in space.

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if not nums:
            return 0
        
        p1, p2 = 1, 1
        last = nums[0]
        
        while p2 < len(nums):
            if nums[p2] != last:
                nums[p1] = nums[p2]
                last = nums[p2]
                p1 += 1
            
            p2 += 1
        
        return p1

[LeetCode] 25. Reverse Nodes in k-Group

Problem : https://leetcode.com/problems/reverse-nodes-in-k-group/

This problem needs to be solved by 2 nested recursion. The outer recursion locates the groups of k nodes. The inner recursion reverse the located group.

Time Complexity :  O ( N )

Space Complexity : O ( 1 ) 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        
        # find the first k nodes
        i = 0
        p = head
        
        while i < k and p:
            p = p.next
            i += 1
        
        # return the original list if it has less nodes than k
        if i < k:
            return head
        
        # reverse the first k nodes
        pre = None
        cur = head
               
        while cur != p:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        
        # append to the rest reversed groups
        head.next = self.reverseKGroup(p, k)
    
        return pre

Updated on 07/18/2021. Update for a simpler recursive solution.

[LeetCode] 24. Swap Nodes in Pairs

Problem : https://leetcode.com/problems/swap-nodes-in-pairs/

Swap nodes in pairs recursively.

Time Complexity : O ( N ) ,  N = length of list

Space Complexity: O ( 1 ),  swap in space.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        if head and head.next:
            tmp = head.next.next
        
            left, right = head, head.next
            
            right.next = left
            left.next = self.swapPairs(tmp)
            
            return right
        
        return head

[LeetCode] 23. Merge k Sorted Lists

Problem : https://leetcode.com/problems/merge-k-sorted-lists/

Must divide and conquer approach to avoid exceeding time limit. 

Time Complexity = O( N log(len(lists) )

Space Complexity: O(1)

 
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
    
        def merge(l1, l2):
            if l1 and l2:
                if l1.val < l2.val:
                    l1.next = merge(l1.next, l2)
                    return l1
                else:
                    l2.next = merge(l1, l2.next)
                    return l2
                
            return l1 if l1 else l2
        
        
        def helper(left, right):
            if left == right:
                return None
            
            if right - left == 1:
                return lists[left]
            
            if right - left == 2:
                return merge(lists[left], lists[left+1])
            
            
            mid = left + (right - left) // 2
            return merge(helper(left, mid), helper(mid, right))
    
            
        return helper(0, len(lists))

Use priority queue to merge K sorted list. N = max length of lists

Time Compleixty = O(N * Log K)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) pq.offer(head);
        }
        
        while (!pq.isEmpty()) {
            p.next = pq.poll();
            p = p.next;
            if (p.next != null) pq.offer(p.next);
        }

        return dummy.next;
    }
}

[LeetCode] 22. Generate Parentheses

Problem : https://leetcode.com/problems/generate-parentheses/

Recursively add open bracket and close bracket for valid sequence.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def helper(left, right, tmp):
            if left == right == n:
                yield "".join(tmp)
            else:
                if left < n:
                    tmp.append("(")
                    yield from helper(left + 1, right, tmp)
                    tmp.pop()
                
                if left > right:
                    tmp.append(")")
                    yield from helper(left, right + 1, tmp)
                    tmp.pop()
        
        return list(helper(0, 0, []))

Edited on 06/16/2021. Refactor by using 'yield'.

[LeetCode] 21. Merge Two Sorted Lists

Problem : https://leetcode.com/problems/merge-two-sorted-lists/

It is intuitive to create a dummy head then iteratively merge the 2 given sorted lists. 

[LeetCode] 20. Valid Parentheses

Problem : https://leetcode.com/problems/valid-parentheses/

Use stack to check if the close parenthesis match with the open parenthesis.

Time complexity: O( len(s) )

Space complexity: O( len(s) )

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairs = new HashMap<>() {
            {
                put('(', ')');
                put('[', ']');
                put('{', '}');
            }
        };
        
        for (char a : s.toCharArray()) {
            if (pairs.containsKey(a)) {
                stack.push(a);
            } else {
                if (stack.isEmpty() || pairs.get(stack.pop()) != a) return false;
            }
        }
        
        return stack.isEmpty();
    }
}

Edited on 03/12/2022. Use map to pair brackets.

[LeetCode] 19. Remove Nth Node From End of List

Problem : https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Use 2 pointers to iterate the linked list. The second pointer is n steps behind the first pointer.

Time Complexity :  O ( N )

Space Complexity : O ( 1 )

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        
        # use dummy head node to handle the case that needs to remove the first node.
        dummy = ListNode(0)
        dummy.next = head
        
        p1, p2 = dummy, dummy
        
        while p2 and n >= 0:
            p2 = p2.next
            n -= 1
            
        while p2 and p1:
            p2 = p2.next
            p1 = p1.next
            
        if p1 and p1.next:
            p1.next = p1.next.next
    
        
        return dummy.next

[LeetCode] 18. 4Sum

Problem : https://leetcode.com/problems/4sum/

Similar to 3Sum.

Time Complexity : O ( len(nums) *len(nums) * len(nums)/2 )

Space Complexity: O (len(nums)*len(nums)*len(nums)*len(nums))

 
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        nums.sort()
        L = len(nums)
        
        result = []
        
        for i in range(L-3):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            for j in range(i+1, L-2):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue
                    
                left, right = j + 1, L - 1
                
                while left < right:
                    # early termination
                    if nums[i] + nums[j] + nums[left] + nums[left] > target:
                        break
                        
                    tmp = nums[i] + nums[j] + nums[left] + nums[right]
                    
                    if tmp < target:
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                    elif tmp > target:
                         l = right - 1
                         while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                         right = l
                    else:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                        
                        l = right - 1
                        while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                        right = l
                        
        return result

[LeetCode] 17. Letter Combinations of a Phone Number

Problem : https://leetcode.com/problems/letter-combinations-of-a-phone-number/

This is a typical backtracking problem. Consider the code travels a tree. Each digit is represented as a node of this tree. Each node has the rest digits as its child node. On each node, the code has number N of letter to pick up. So the code does DFS on this tree to find all of the combination.

To simplify the calculation, consider each digits has 3 letters.

Time Complexity :  O ( 3 ** len(s) )

Space Complexity:  O ( 3 ** len(s) )

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9":"wxyz"}
        
        result = []
        
        def backtrack(i, tmp):
            if i == len(digits):
                if tmp:
                    result.append(tmp)
                return
                
            for t in letters[digits[i]]:
                backtrack(i+1, tmp + t)
        
        backtrack(0, "")
        
        return result

BFS based solution:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9":"wxyz"}
        
        if not digits: return []
                
        result = []
        
        queue = deque([[l, 1] for l in letters[digits[0]]])
     
        while queue:
            for _ in range(len(queue)):
                w , index = queue.popleft()
                
                if index == len(digits):
                    result.append(w)
                else:
                    for l in letters[digits[index]]:
                        queue.append([w + l, index + 1])
        
        return result

An iterative solution. Start from the last digit to the first digit, add letter of current digit to the front of last letter combinations.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        
        letters = {'2': 'abc', '3': 'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz' }
              
        ds = [d for d in digits]
        
        result = [[l] for l in letters[ds.pop()]]
        
        while ds:
            suffix = result[:]
            result = []
            
            for l in letters[ds.pop()]:
                for s in suffix:
                    result.append([l] + s)
            
        return [''.join(t) for t in result]

Edited 04/24/2021. Add the iterative solution.

[LeetCode] 16. 3Sum Closest

Problem : https://leetcode.com/problems/3sum-closest/

Use the same two pointers approach as the 3Sum quiz.

Time Complexity :  O ( N * LogN + N ** 2 )

Space Complexity: O ( log N ) or O ( N ), depending on the sort algorithm. 

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        nums.sort()
        N = len(nums)
        
        result = nums[0] + nums[1] + nums[2] # assume the init value of result
        
        for i in range(N-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            left, right = i + 1, N-1
                        
            while left < right:
                tmp = sum([nums[i], nums[left], nums[right]])
                
                if abs(result - target) > abs(tmp - target):
                    result = tmp
                
                if tmp == target:
                    return target
                
                if tmp < target:
                    j = left + 1
                    while j < right and nums[j] == nums[left]:
                        j += 1
                    left = j
                else:
                    k = right - 1
                    while k > left and nums[k] == nums[right]:
                        k -= 1
                    right = k
                    
        return result

Edited of 07/27/2021. Update result variable's init value.