[LeetCode] 941. Valid Mountain Array

 Problem : https://leetcode.com/problems/valid-mountain-array/

Simulate the validation process.

class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) return false;
        
        int i = 0;
        
        // is strictly increasing
        while (i + 1 < arr.length && arr[i] < arr[i+1]) {
            i += 1;
        }
        
        if (i == 0 || i + 1 == arr.length) return false;
      
        // is strictly decreasing
        while (i + 1 < arr.length && arr[i] > arr[i+1] ) {
            i += 1;
        }
        
        return i+1 == arr.length;
    }
}

[LeetCode] 1200. Minimum Absolute Difference

 Problem : https://leetcode.com/problems/minimum-absolute-difference/

Because the minimum difference can only exist between 2 consecutive elements in sorted list.

We sort the input array first, then find the pairs with minimum difference.

Time complexity = O(N * LogN) + O(N),  N = length of the input array.

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int miGlobal = Integer.MAX_VALUE;
        List<List<Integer>> result = new ArrayList();
        
        // minimum absolute difference can only exist between 2 consecutive elements
        Arrays.sort(arr);
        
        for (int i = 1; i < arr.length; i++) {
            int miLocal = arr[i] - arr[i-1];
            if (miLocal < miGlobal) {
                // start a new result when find a new minimum difference
                miGlobal = miLocal;
                result = new ArrayList(Arrays.asList(Arrays.asList(arr[i-1], arr[i])));
            } else if (miLocal == miGlobal) {
                // otherwise append this new pair to the result list.
                result.add(Arrays.asList(arr[i-1], arr[i]));
            }
        }
        
        return result;
    }
}

Because the value range of the input array is from -10^6 to 10^6, the input array can be sorted with counting sort approach which Time complexity is O(N)

[LeetCode] 448. Find All Numbers Disappeared in an Array

 Problem : https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Because all numbers in the array is in the range [1, n].  If all numbers exist in the array, we can always swap the numbers to make nums[i] = i + 1.

So try to swap the number to its correct position. Then iterate the array to find the missing number which nums[i] != i + 1

class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<int> {
        for (i in 0 until nums.size) {
            while (nums[i] != i+1) {
                if (nums[nums[i] - 1] == nums[i]) {
                    break
                }
                
                val tmp = nums[nums[i] - 1]
                nums[nums[i] - 1] = nums[i]
                nums[i] = tmp
            }
        }
        
        val result = mutableListOf<int>()
        
        for (i in 0 until nums.size) {
            if (nums[i] != i + 1) {
                result.add(i+1)
            }
        }
        
        return result
    }
}

[LeetCode] 915. Partition Array into Disjoint Intervals

 Problem : https://leetcode.com/problems/partition-array-into-disjoint-intervals/

The requirement of all numbers in left sub-array are less than or equal to numbers in right sub-array can be interpreted as the maximum number in left sub-array is less than or equal to the minimum number in right sub-array.

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        N = len(nums)
        
        # maximum number from left of nums[i] ( includes nums[i] )
        maxFromLeft = [0] * N
        maxFromLeft[0] = nums[0]
        
        for i in range(1, N):
            maxFromLeft[i] = max(maxFromLeft[i-1], nums[i])
        
        # minimum number from right of nums[i]
        minFromRight = nums[N-1]
        result = N-1
        
        for i in reversed(range(1, N)):
            minFromRight = min(minFromRight, nums[i])
            
            if minFromRight >= maxFromLeft[i-1]:
                result = i
        
        return result

[LeetCode] 334. Increasing Triplet Subsequence

Problem : https://leetcode.com/problems/increasing-triplet-subsequence/

Use 2 caches to save the minimal number from left and the maximal number from right of each position.

Return true when minimal_from_left < nums[i] < maximal_from_right.

Time Complexity = O ( N )

Space Complexity = O ( 2 * N )

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        mi = [0] * len(nums)
        mx = [0] * len(nums)
        
        mi_so_far = nums[0]
        for i in range(len(nums)):
            mi_so_far = min(mi_so_far, nums[i])
            mi[i] = mi_so_far
        
        mx_so_far = nums[-1]
        for i in reversed(range(len(nums))):
            mx_so_far = max(mx_so_far, nums[i])
            mx[i] = mx_so_far
        
        for i in range(len(nums)):
            if mi[i] < nums[i] < mx[i]:
                return True
        
        return False

Space Complexity O(1) Solution:

Use 2 pointers m1, m2 to save number with smaller value.

It finds the increasing triplet when find a number larger than both m1 and m2.

 
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        m1 = m2 = 2 ** 31 - 1 #MAX_INT
        
        for n in nums:
            if m1 >= n : 
                m1 = n
            elif m2 >= n :
                # find m2 > m1
                m2 = n
            else:
                # find m3 > m2 > m1
                return True
        
        return False

[LeetCode] 289. Game of Life

 Problem : https://leetcode.com/problems/game-of-life/

Use bit mask to save the next-state on high-order bits.

Time Complexity = O ( M * N )

Space Complexity = O ( 1 )

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        ROW = len(board)
        if ROW == 0: return 
        
        COLUMN = len(board[0])
        if COLUMN == 0: return
        
        def alive(y,x):
            return 0 <= y < ROW and 0 <= x < COLUMN and board[y][x] & 1 == 1
        
        def nextState(y,x):
            aliveCount = 0
            
            for dy in [-1, 0, 1]:
                for dx in [-1, 0, 1]:
                    if dy == 0 and dx == 0:
                        continue
                    
                    if alive(y+dy, x+dx):
                        aliveCount += 1
            
            """
            Any live cell with fewer than two live neighbors dies as if caused by under-population.
            Any live cell with two or three live neighbors lives on to the next generation.
            Any live cell with more than three live neighbors dies, as if by over-population.
            Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
            """
            
            # dead
            nextState = 0
            
            if board[y][x] == 1:
                if aliveCount < 2:
                    # dead
                    pass
                elif 2 <= aliveCount <= 3:
                    # alive
                    nextState = 1 << 3
                else:
                    # dead
                    pass
            else:
                if aliveCount == 3:
                    # alive
                    nextState = 1 << 3
                else:
                    # dead
                    pass
            
            board[y][x] |= nextState
                    
        
        def normalizeState(y,x):
            board[y][x] = 1 if board[y][x] & (1<<3) else 0
        
        for y in range(ROW):
            for x in range(COLUMN):
                nextState(y, x)
        
        for y in range(ROW):
            for x in range(COLUMN):
                normalizeState(y, x)                

[LeetCode] 238. Product of Array Except Self

Problem : https://leetcode.com/problems/product-of-array-except-self/

Product of Array can be calculated with the table like:

    
    0   1   2   3
  +---+---+---+---+
0 |   | * | * | * | 
  +---+---+---+---+
1 | * |   | * | * |
  +---+---+---+---+
2 | * | * |   | * |
  +---+---+---+---+
3 | * | * | * |   |
  +---+---+---+---+

As it shows,  result[i]  = product(num[:i])  * product(nums[i:])

Let dp1[i] = product of numbers before nums[i], not include nums[i],

And dp2[i] = product of numbers after nums[i], not include nums[i]

Then result[i] = dp1[i] * dp2[i]

Time Complexity = O ( N )

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        N = len(nums)
        
        # dp1[i] = product of numbers before nums[i], not include nums[i]
        dp1 = [1] * N
        
        # dp2[i] = product of numbers after nums[i], not include nums[i]
        dp2 = [1] * N
        
        for i in range(1, N):
            dp1[i] = nums[i-1] * dp1[i-1]
            
        for i in reversed(range(N-1)):
            dp2[i] = nums[i+1] * dp2[i+1]
        
        return[ dp1[i] * dp2[i] for i in range(N) ]

[LeetCode] 228. Summary Ranges

Problem : https://leetcode.com/problems/summary-ranges/

For number A,  create the initial range [A, A].  If the next number B = A + 1, then extends the range as [A, B]. Otherwise create new initial range [B, B] and append to the result list.

Time Complexity = O ( N )

Space Complexity = O ( N )

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        result = []
        
        for n in nums:
            if result and n == result[-1][1] + 1:
                result[-1][1] = n
            else:
                result.append([n, n])
        
        return ["{}->{}".format(a, b) if a != b else "{}".format(a) for a, b in result]

[LeetCode] 205. Isomorphic Strings

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

Because we can use any character to update s. Only the relative position of characters matters.

Use the first pos of one character to encode the input string. Then check if the 2 encoded strings are identical.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        def encode(word):
            seen = {}
           
            for i, x in enumerate(word):
                if x not in seen: 
                    seen[x] = i
                yield seen[x]
            
        
        return all(map(lambda x: x[0] == x[1], zip(encode(s), encode(t))))

Updated on 07/12/2021. Update for a simpler solution.

[LeetCode] 189. Rotate Array

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

A solution uses separate cache.

Time Complexity = O ( N )

Space Complexity = O ( N )

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        offset = len(nums) - (k % len(nums))
        
        tmp = nums[offset:] + nums[:offset]
        
        for i in range(len(nums)):
            nums[i] = tmp[i]

Reverse 3 times solution:

Time Compelxity = O ( N )

Space Complexity = O ( 1 )

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        def reverse(left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
            
        
        N = len(nums)
        pivot = N - k % N
        
        # reverse the left side of pivot
        reverse(0, pivot-1)
        # reverse the right side of pivot
        reverse(pivot, N-1)
        # reverse the entire array
        reverse(0, N-1)

[LeetCode] 128. Longest Consecutive Sequence

Problem : https://leetcode.com/problems/longest-consecutive-sequence/

Hash table based solution:

Store the input numbers in Set. Then lookup for consecutive sequence if current number does not have preceding number.

Time Complexity = O ( N )

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        memo = set(nums)
        
        result = 0
        
        for n in nums:
            if n - 1 not in memo:
                tmp = 1
            
                while n + 1 in memo:
                    tmp += 1
                    n += 1
            
                result = max(result, tmp)
        
        return result

Union-Find based solution:

Put the contiguous numbers in one group. Then find the maximum number of items in one group.

class UnionFind:
    def __init__(self, nums):
        self.memo = {}
        for n in nums:
            self.memo[n] = n
    
    def union(self, x, y):
        parent = y
        while parent != self.memo[parent]:
            tmp = self.memo[parent]
            self.memo[parent] = self.memo[x]
            parent = tmp
            
        self.memo[y] = self.memo[x]
    
    def find(self, x):
        if x not in self.memo:
            return None
        
        parent = self.memo[x]
        
        while self.memo[parent] != parent:
            parent = self.memo[parent]
    
        while self.memo[x] != parent:
            tmp = self.memo[x]
            self.memo[x] = parent
            x = tmp
            
        return parent

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        uf = UnionFind(nums)
        
        for n in nums:
            if uf.find(n-1) != None:
                uf.union(n-1, n)
            
            if uf.find(n+1) != None:
                uf.union(n, n+1)
        
        maxLength  = defaultdict(int)
        
        # count number of items in each group
        for k in uf.memo.keys():
            p = uf.find(k)
            maxLength[p] += 1
        
        return max(maxLength.values()) if maxLength.values() else 0

[LeetCode] 122. Best Time to Buy and Sell Stock II

Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ 

Should collect every possible profit

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        
        profit = 0
        buyin = prices[0]
        
        for i in range(1, len(prices)):
            p = prices[i]
            if p > buyin:
                profit += p - buyin
            
            buyin = p
            
        return profit

One liner solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum(b - a for a, b in zip(prices, prices[1:]) if b > a)

Edited on 11/09/2021. Add the one liner solution.

[LeetCode] 121. Best Time to Buy and Sell Stock

Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Maximum profit =  buy at the lowest price and sell at the highest price.

Time Complexity = O ( N )

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minSoFar = 2 ** 31 - 1
        profit = 0
        
        for p in prices:
            profit = max(profit, p - minSoFar)
            minSoFar = min(minSoFar, p)
        
        return profit

A greedy solution :

Time Complexity = O ( N )

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        localmax, globalmax = 0, 0
        
        for i in range(1, len(prices)):
            localmax = max(localmax + prices[i] - prices[i-1], 0)
            globalmax = max(localmax, globalmax)
        
        return globalmax

Use localmax to save the maximum profit can get with consecutive days.

If localmax <  0, set localmax = 0 to restart.

Use globalmax to save the maximum localmax be found.

DP solution:

On each day, we either hold stock or sell stock.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        holdStock = -prices[0]
        notHoldStock = 0
        
        for i in range(1, len(prices)):
            # keep holding stock or buy stock
            # don't accumulate profit, since it can only buy once
            holdStock = max(holdStock, -prices[i])
            
            # keep not holding stock or sell stock
            notHoldStock = max(notHoldStock, holdStock + prices[i])
        
              
        # on the last day, we get the maximum profit when not hold any stock
        return notHoldStock

[LeetCode] 119. Pascal's Triangle II

Problem : https://leetcode.com/problems/pascals-triangle-ii/

Time Complexity = O ( N * N )

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        result = [1] * (rowIndex + 1)
        
        for i in range(2, rowIndex+1):
            preceding_number = result[0]
            for j in range(1, i):
                tmp = result[j]
                result[j] = preceding_number + result[j]
                preceding_number = tmp
        
        return result

[LeetCode] 118. Pascal's Triangle

Problem : https://leetcode.com/problems/pascals-triangle/

Calculate current line base on the last line numbers.

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = []
        
        if numRows <= 0:
            return result
    
        for i in range(numRows):
            result.append([1] * (i+1))
            
        for i in range(2, numRows):    
            for j in range(1, i):
                result[i][j] = result[i-1][j-1] + result[i-1][j]
            
        return result

[LeetCode] 73. Set Matrix Zeroes

Problem : https://leetcode.com/problems/set-matrix-zeroes/

Allocate extra space to record columns or rows have 0.

Space complexity O ( ROW + COLUMN ) solution. 

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        mark = [False] * (ROW + COLUMN)
        
        for y in range(ROW):
            for x in range(COLUMN):
                if matrix[y][x] == 0:
                    mark[y] = True
                    mark[ROW + x] = True
        
        # set zeros 
        for y in range(ROW):
            for x in range(COLUMN):
                if mark[y] or mark[ROW + x]:
                    matrix[y][x] = 0

Edited on 08/13/2021. Simplify the O(ROW + COLUMN) 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] 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] 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