[Leetcode] Array

Posted on | In , |

Introduction

  • Can operate efficiently on both ends
  • Be comfortable with with writing code on subarrays
  • Sometimes may need a helper array to solve the problems

List in Python: list in python is dynamically re-sized

Syntax

Python:

1
2
3
4
A.append(42)
A.remove(2) # O(n)
A.insert(3, 28) # O(n)
a in A # O(n)

JS:

1
2
3
4
A.push(42)
A.pop() // Remove from end
A.unshift(2) // Insert from start
A.shift() // Remove from start

Instantiate a 2-D array:
Python:

1
2
3
# Creates a list containing 5 lists, each of 8 items, all set to 0
w, h = 8, 5;
Matrix = [[0 for x in range(w)] for y in range(h)]# Creates a list containing 5 lists, each of 8 items, all set to 0

JS:

1
const matrix = new Array(5).fill(0).map(() => new Array(4).fill(0)); // 5 rows, 4 columns matrix filled with 0

Copy a list in python

Shallow Copy
Python

1
2
newList = oldList[:]
newList = list(oldList)

Javascript

1
2
3
const A = [{'a': 1, 'b': 2}];
const B = A.slice(0);
const C = [...A];

Deep Copy
Python

1
2
from copy import deepcopy
newList = deepcopy(oldList)

Javascript

1
let B = JSON.parse(JSON.stringify(A)); // Limitation: A can't contain undefined or functions

Methods

Python:

1
2
3
4
5
6
7
8
9
min(A)
max(A)
# Binary Search in a sorted array
bisect.bisect(A, 6)
A.reverse() # In place
A.sort() # In place
sorted(A) # Returns a copy
del A[i]
del A[i:j] # Removes the slice

Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
Math.min(...A);
// Reverse 
B = A.reverse();

// From 
B = Array.from('foo'); //['f', 'o', 'o']

// Concat: returns a new array
A = ['a', 'b', 'c'];
B = ['d', 'e', 'f'];
C = A.concat(B);

// Find: Return the first item in the array
A = [1, 2, 3]
A.find(ele => ele > 1) // return 2

// Filter
A = [1,2,3,4,5];
A.filter(ele => ele > 2); // return [3,4,5]

// Flat
A = [1, 2, [3, 4, [5, 6]]];
A.flat(); //[1, 2, 3, 4, [5, 6]]
// Alternative: reduce + concat
A.reduce((acc, val) => val.concat(acx), []); // Same as flat()

// forEach
A.forEach(ele => console.log(ele))

// Join
A = ['a', 'b','c'];
A.join(',');

// Map: returns a new array
A = [1,2,3];
B = A.map(ele => ele * 2);

// Reduce:
A = [1,2,3];
result = A.reduce((acc, val) => val + acx, 0) // 0 is the initial value
// The reducer function takes: acc, val, idx(current index), src(source array)

// Some: test whether at least one element in the array passes the function
A.some(ele => ele % 2 == 0); // true

Slicing and list comprehension

Python

1
2
3
4
5
A[k:] + A[:k] # Rotates A by k to the left

[x**2 for x in range(6) if x % 2 == 0]
[(x, y) for x in A for y in B]
[[x**2 for x in row] for row in M]

Javascript
slice() provides a shallow copy of a portion of the original array.

1
2
3
A = [1,2,3,4,5];
A.slice(2); // [3,4,5]
A.slice(1,4); // [2,3,4]

Splice in javascript

The splice() method changes the contents of an array by removing or replacing existing elements and/or adding new elements in place.

splice() can be used to do:

  • remove element from any index of array
  • replace element from any index of array
  • insert new element from any index of array
1
2
3
4
5
6
7
8
9
10
let A = ['a', 'c', 'd'];
// Insert
A.splice(1, 0, 'b'); // Remove 0 elements at index 1, insert 'b'
// A -> ['a','b', 'c', 'd']
// Remove
A.splice(3, 1); // Remove 1 element at index 3
// A -> ['a', 'b', 'c']
// Replace
A.splice(2, 1, 'd'); // Remove 1 element at index 2, insert 'd'
// A -> ['a', 'b', 'd']

Problems

Dutch National Flag

Leetcode: 75. Sort Colors

Solution

  • Time: O(n), Space: O(1)
  • Similiar to quick sort
  • Set three dividers: small, cur, and big
  • Divide the array into four sections: [0,0,1,1,???,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var sortColors = function(nums) {
    let small = 0;
    let big = nums.length - 1;
    let cur = 0;
    while (cur <= big) {
        if (nums[cur] === 0) {
            let temp = nums[cur];
            nums[cur] = nums[small];
            nums[small] = temp;
            small ++;
            cur ++;
        } else if (nums[cur] === 1) {
            cur++;
        } else {
            let temp = nums[cur];
            nums[cur] = nums[big];
            nums[big] = temp;
            big --;
        }
    }
};

Note:

  1. if nums[cur] != 2 is used to avoid cases like [2,1,2] where you could switch 2 with 2 and move forward cur, and left 2 at a wrong place
  2. Ending point is cur <= r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def sortColors(self, nums):
    if len(nums) < 2:
        return nums
    l, r = 0, len(nums) - 1
    cur = 0
    while cur <= r:
        if nums[cur] == 0:
            nums[l], nums[cur] = nums[cur], nums[l]
            l += 1
        if nums[cur] == 2:
            nums[r], nums[cur] = nums[cur], nums[r]
            r -= 1
            if nums[cur] == 0:
                nums[l], nums[cur] = nums[cur], nums[l]
                l += 1
        if nums[cur] != 2:
            cur += 1

Subarray problems

Kadane’s Algorith: Video: https://www.youtube.com/watch?v=86CQq3pKSUw

Permutation Problems

  • Every permutation can be represented by a collection of independent permutations, each of which is cyclic, that is, it moves all elements by a fixed offset, wrapping around.
  • There exist exactly n! permutations of n elements

EPI 5.10 Permutate the elements of an array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def apply_permutation(perm, A):
    """
    Given an array A [a,b,c,d] and a permutation [2,0,1,3]
    Apply permutation to A in a constant space cost
    Solution: In order to remember which location is already permutated, we use perm[cur] - n to make sure every permutated location is negative. After one permutation cycle, we look for the next cycle.
    """
    n = len(A)
    for i in range(len(A)):
        if perm[i] < 0:
            continue
        cur = i
        nxt = perm[cur]
        temp = A[i]
        while temp != A[nxt]:
            prev = A[nxt]
            A[nxt] = temp
            temp = prev
            perm[cur] = perm[cur] - n
            cur = nxt
            nxt = perm[cur]

31. Next Permutation

Great Video: https://www.youtube.com/watch?v=GCm7m5671Ps

Find pattern

[Solution]:

  1. Find k such that p[k] < p[k + 1] and entries after k appear in decreasing order
  2. Find the smallest p[l] such that p[l] > p[k]
  3. Swap p[l] and p[k]
  4. Reverse the sequence after position k

Note that decreasing order including p[k] = p[k + 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def nextPermutation(nums: List[int]) -> None:
    tail = len(nums) - 1
    if len(nums) == 1:
        return
    # Find the largest k before descending tail
    while tail - 1 > 0 and nums[tail - 1] >= nums[tail]:
        tail -= 1
    
    minLarge = len(nums) - 1
    while minLarge >= 0 and nums[minLarge] <= nums[tail - 1]:
        minLarge -= 1
    if minLarge < 0:
        nums[0:] = nums[::-1] # Reverse 
        return
    nums[minLarge], nums[tail - 1] = nums[tail - 1], nums[minLarge]
    nums[tail:] = nums[tail:][::-1]

1053. Previous Permutation With One Swap

Leetcode: https://leetcode.com/problems/previous-permutation-with-one-swap/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def prevPermOpt1(self, A: List[int]) -> List[int]:
        # From tail, find the first pair of decreasing number
        n = len(A)
        minlist = A[::]
        for i in reversed(range(n - 1)):
            minlist[i] = min(minlist[i], minlist[i + 1])
        for i in reversed(range(n)):
            if A[i] > minlist[i]:
                j = i + 1
                while j < n and A[j] < A[i]:
                    j += 1
                A[i], A[j - 1] = A[j - 1], A[i]
                break
        return A

Streaming data problems

295. Find Median from Data Stream

Leetcode: https://leetcode.com/problems/find-median-from-data-stream/

EPI 5.13 Sample Online Data

Design a program that takes a input of size k, and reads packets, continuously maintaining a uniform random subset of size k of the read packets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Assumption: there are at least k elements in the stream.
def online_random_sample(stream, k):
    """
    stream: list_iterator: [p,q,r,t,u,v]
    k: int: 2
    return: random subset of length k of stream
    """
    from random import choices
    import random
    res = [0] * k
    chs = [0,1]
    cnt = 0
    for cur in stream:
        if cnt < k:
            res[cnt] = cur
        else:
            p = k / (cnt + 1)
            weights = [1 - p, p]
            replace = choices(chs, weights)[0]
            if replace > 0:
                # randomly select one from current
                replace = random.randint(0, k - 1)
                res[replace] = cur
        cnt += 1
    return res

2D-Array Problems

To manipulate a 2D array, we always use left, top, right, bottom four pointers as boundaries.

48. Rotate Image

Leetcode: https://leetcode.com/problems/rotate-image/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def rotate(self, matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    if not matrix or not matrix[0]:
        return matrix
    top = left = 0
    bottom = right = len(matrix) - 1
    # get 4 corners
    def rotate_layer(top, left, bottom, right):
        for i in range(0, right - left):
            c1 = [top, left + i]
            c2 = [top + i, right]
            c3 = [bottom, right - i]
            c4 = [bottom - i, left]
            # one move
            temp = matrix[c4[0]][c4[1]]
            matrix[c4[0]][c4[1]] = matrix[c3[0]][c3[1]]
            matrix[c3[0]][c3[1]] = matrix[c2[0]][c2[1]]
            matrix[c2[0]][c2[1]] = matrix[c1[0]][c1[1]]
            matrix[c1[0]][c1[1]] = temp
    while top < bottom:
        rotate_layer(top, left, bottom, right)
        top += 1
        left += 1
        bottom -= 1
        right -= 1

54. Spiral Matrix

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]:
        return []
    top = 0
    bottom = len(matrix) - 1
    left = 0
    right = len(matrix[0]) - 1
    i = j = 0
    res = []
    nums = len(matrix) * len(matrix[0])
    cnt = 1
    while top <= bottom and left <= right:
        
        for j in range(left, right + 1):
            res.append(matrix[top][j])
        
        for i in range(top + 1, bottom + 1):
            res.append(matrix[i][right])
        
        if top < bottom and left < right:
            for j in reversed(range(left, right)):
                res.append(matrix[bottom][j])
                
            for i in reversed(range(top + 1, bottom)):
                res.append(matrix[i][left])

        top += 1
        bottom -= 1
        right -= 1
        left += 1
    return res

1072. Flip Columns For Maximum Number of Equal Rows

Leetcode: https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/

Solution:
Find the “pattern” of the row. “Pattern” here can be characterized by whether each element in the row is different with the first element or not. 

1
2
3
4
5
6
7
8
9
10
11
12
13
def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
    if not matrix or not matrix[0]:
        return 0
    d = collections.defaultdict(int)
    for row in matrix:
        pattern = ""
        for cell in row:
            if cell == row[0]:
                pattern += "a"
            else:
                pattern += "b"
        d[pattern] += 1
    return max(list(d.values()))

Duplicates or Missing numbers

448. Find All Numbers Disappeared in an Array

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

Find a missing number in O(n) time with no extra space:

1
2
3
4
5
6
7
8
9
10
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    n = len(nums)
    for i in range(n):
        cur = abs(nums[i]) - 1
        nums[cur] = -abs(nums[cur])
    res = []
    for i in range(n):
        if nums[i] > 0:
            res.append(i + 1)
    return res

442. Find All Duplicates in an Array

Leetcode: https://leetcode.com/problems/find-all-duplicates-in-an-array/

Note:
In order to achieve O(1) space, we use array itself as the marker of visited element.

1
2
3
4
5
6
7
8
9
def findDuplicates(self, nums):
    res = []
    for num in nums:
        if nums[abs(num) - 1] < 0:
            # visited num - 1th value
            res.append(abs(num))
        else:
            nums[abs(num) - 1] = -abs(nums[abs(num) - 1])
    return res

Majority Element problem

Algorithm: Boyer-Moore Voting Algorithm

Majority Voting Algorithm

169. Majority Element

Leetcode: https://leetcode.com/problems/majority-element/

Video: https://www.youtube.com/watch?v=zOyOwDEF1Rc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var majorityElement = function(nums) {
    let major = nums[0];
    let cnt = 1
    for (let i = 1; i < nums.length; i++) {
        if (cnt === 0) {
            major = nums[i];
            cnt = 1;
        } else {
            if (nums[i] === major) {
                cnt++;
            } else {
                cnt--;
            }
        }
    }
    return major;
};

229. Majority Element II

Leetcode: https://leetcode.com/problems/majority-element-ii/

Since the questions is asking element that has frequency < n / 3, there are at most two answers in the result array. We can use two candidates and two counters to keep track of two most frequent element in the list.

443. String Compression

Leetcode: https://leetcode.com/problems/string-compression/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var compress = function(chars) {
    if (chars.length <= 1) { return chars.length; }
    let res = chars.length;
    let curIndex = 0;
    let left = 0;
    let right = 0;
    while (right < chars.length) {
        while (chars[right] === chars[left]) { right++ }
        if (right - left > 1) {
            res -= right - left - 1;
            res += ((right - left).toString()).length;
        }
        chars[curIndex++] = chars[left];
        if (right - left > 1) {
            for (let ch of (right - left).toString()) {
                chars[curIndex++] = ch;
            }
        }
        left = right;
    }
    return res;
};

Nested Array Problem

339. Nested List Weight Sum

Leetcode: https://leetcode.com/problems/nested-list-weight-sum/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def depthSum(self, nestedList):
    """
    :type nestedList: List[NestedInteger]
    :rtype: int
    """
    self.res = 0
    def dfs(curList, depth):
        if curList.isInteger():
            self.res += curList.getInteger() * depth
        else:
            for elem in curList.getList():
                dfs(elem, depth + 1)
    
    for item in nestedList:
        dfs(item, 1)
    return self.res

364. Nested List Weight Sum II

Leetcode: https://leetcode.com/problems/nested-list-weight-sum-ii/

Instead of multiply the depth, we simply add sum from the previous level again in the next level with hist representing history.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def depthSumInverse(self, nestedList):
    """
    :type nestedList: List[NestedInteger]
    :rtype: int
    """
    hist = 0
    res = 0
    while nestedList:
        next_level = []
        for elem in nestedList:
            if elem.isInteger():
                hist += elem.getInteger()
            else:
                next_level = elem.getList() + next_level
        res += hist
        nestedList = next_level
    return res

341. Flatten Nested List Iterator

Leetcode: https://leetcode.com/problems/flatten-nested-list-iterator/

Error Case I: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# input: [[]]
# expected: []
# My original solution:
def hasNext(self):
    """
    :rtype: bool
    """
    return self.list

# Correct solution
def hasNext(self):
    try:
        self.value = next(self.g)
        return True
    except StopIteration:
        return False

Generator Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class NestedIterator(object):
    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        self.list = nestedList
        self.g = self.generator()
        
        
    def generator(self):
        while self.list:
            cur = self.list.pop(0)
            if cur.isInteger():
                yield cur.getInteger()
            else:
                self.list = cur.getList() + self.list
        
    def next(self):
        """
        :rtype: int
        """
        return next(self.g)

    def hasNext(self):
        try:
            self.value = next(self.g)
            return True
        except StopIteration:
            return False

Stack solution
Use a stack to flatten list. The index in each list represents the current element that’s dealing with.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class NestedIterator(object):
    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        self.stack = [[nestedList, 0]]
        
    def next(self):
        curList, i = self.stack[-1]
        self.stack[-1][1] += 1
        return curList[i].getInteger()

    def hasNext(self):
        s = self.stack
        while s:
            curList, i = s[-1]
            if i == len(curList): # finish this layer
                s.pop()
            else:
                elem = curList[i]
                if elem.isInteger():
                    return True
                s[-1][1] += 1
                s.append([elem.getList(), 0])
        return False

1 or 2 passes from left to right/right to left:

845. Longest Mountain in Array

Leetcode: https://leetcode.com/problems/longest-mountain-in-array/

My Solution: Look for the peak in range A[1, len(A) - 1], for each peak, we expand right and left border to get the maximum length.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def longestMountain(self, A):
    """
    :type A: List[int]
    :rtype: int
    """
    if len(A) < 3:
        return 0
    res = 0
    i = 1
    while i < len(A) - 1:
        if A[i - 1] >= A[i] or A[i + 1] >= A[i]:
            i += 1
            continue
        l, r = i - 1, i + 1
        length = 1 
        if A[l] < A[i] and A[i] > A[r]:
            length += 2
        while l > 0 and A[l - 1] < A[l]:
            length += 1
            l -= 1
        while r < len(A) - 1 and A[r + 1] < A[r]:
            length += 1
            r += 1
        res = max(res, length)
        i = r + 1
    return res

Two-pass Solution: Use one up array to remember the length of the continuous increasing sequence before i, and use down to remember the length of the continuous decreasing sequence after i. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestMountain(self, A: List[int]) -> int:
    if len(A) < 3:
        return 0
    up = [0] * len(A)
    down = [0] * len(A)
    res = 0
    for i in range(1, len(A)):
        if A[i] > A[i - 1]:
            up[i] = up[i - 1] + 1
    for i in reversed(range(len(A) - 1)):
        if A[i] > A[i + 1]:
            down[i] = down[i + 1] + 1
            if up[i]:
                res = max(res, up[i] + down[i] + 1)
    return res

One pass solution: Use two variables up and down to keep track of the length of continuous increasing and decreasing subarrays. Reset them to 0 when meeting pivot points.

42. Trapping Rain Water

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

Note: Go from left to right and backwards, and keep finding left and right boundaries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def trap(self, height):
    if len(height) < 2:
        return 0
    l, r = 0, 1
    temp = 0
    res = 0
    while r < len(height):
        if height[r] >= height[l]:
            res += temp
            temp = 0
            l = r
        else:
            temp += height[l] - height[r]
        r += 1
    l, r = len(height) - 2, len(height) - 1
    temp = 0
    while l >= 0:
        if height[l] > height[r]: # ! to prevent duplicates, we only track l > r cases here
            res += temp
            temp = 0
            r = l
        else:
            temp += height[r] - height[l]
        l -= 1
    return res

581. Shortest Unsorted Continuous Subarray

Leetcode: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

Note: Go forward to find the left boundary of unsorted elements, go backwards to find the right boundary of unsorted elements.

  • determine the correct position of the minimum and the maximum element in the unsorted subarray to determine the boundaries of the required unsorted subarray.
  • Time Complexity: O(N), Space: O(2N)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        forward = []
        backward = []
        left, right = float('inf'), -1
        for i in range(len(nums)):
            j = len(nums) - i - 1
            while forward and forward[-1][1] > nums[i]:
                left = min(left, forward.pop()[0])
            forward.append([i, nums[i]])
            while backward and backward[-1][1] < nums[j]:
                right = max(right, backward.pop()[0])
            backward.append([j, nums[j]])
        # ! Remember the case when nums is already sorted
        if left == float('inf') and right == -1:
            return 0
        return right - left + 1

121 Best Time to Buy and Sell Stock
152 Maximum Product Subarray
238 Product of Array Except Self
739 Daily Temperatures
769 Max Chunks to Make Sorted
770 Max Chunks to Make Sorted II
821 Shortest Distance to a Character
845 Longest Mountain in Array

LC 162, LC 852, see https://adonais0.github.io/20181024/leetcode-binary-search-recursion/

Array Manipulation Problem

189. Rotate Array

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

Solve with TC = O(n) and space complexity = O(1)

Note:

  • Start with i = 0, keep putting current element to the correct place, use a temp variable to store the original element at the destination
  • new i = (i + k) % n 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def rotate(self, nums: List[int], k: int) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    i = 0
    n = len(nums)
    if n <= 1:
        return nums
    
    cnt = 0
    cur = 0
    
    while cnt < n:
        i = cur
        prev = nums[i]
        while True:
            newIndex = (i + k) % n
            temp = nums[newIndex]
            nums[newIndex] = prev
            prev = temp
            i = newIndex
            cnt += 1
            if i == cur:# stop when loop back to the start
                break
            if cnt == n:
                return
        cur += 1