41. First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

My accepted code can be found here

Coming up with the way to solve the problem is the most difficult part of the problem. The trick here is we can change the order of the input array in place. So we just place every positive integer i in the index of (i - 1) whenever possible, and at last we traverse the array and find the first index i whose element is not (i + 1). And that’s the answer.

So the algorithm is like:

FirstMissingPositive(a: int[]):
    let i = 0
    for i < length(a):
        if   a[i] <= 0 or a[i] > length(a) // out of range
          or a[i] == i + 1       // already in place
          or a[i] == a[a[i] - 1] // duplication
        then ++i; continue
        else
            swap(nums[i], nums[nums[i] - 1])
    i = 0
    for i < length(a):
        if a[i] != i + 1 then return i + 1
    return i + 1

The time complexity is O(n) since every number would be swap to the right place at most once. Extra space is O(1).

329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4 The longest increasing path is [1, 2, 6, 9].

My accepeted code can be found here

I solve this problem in two searching method, in breadth first and depth first. The overall complexity of two method should be similar, but the actual running time differ a lot. The breadth first algorithm complete in about 350ms but depth first algorithm complete in just 15ms.

I only introduce the depth first search here.

The rational is that the matrix form a acyclic directed graph, with every cell pointing to its neighbours with more value. So we first find the source of the graph, who have only larger neighbours. And do DFS over the sources. Since maximum path length must start with one of those sources, so the maximum answer among the sources is the final result.

So the algorithm is:

LongestIncreasingPathInMatrix(matrix: int[M][N]):
    let start = the array of the coordinates, whose corresponding element in the matrix are the minimums among their neighbour.
    let result = 1
    let memory = int[M][N] filled with -1
    for (i, j) in start:
        result = max(result, DFS(matrix, memory, i, j))
    return result

DFS(matrix: int[M][N], memory: int[M][N], i: int, j: int):
    if memory[i][j] > 0 then return memory[i][j]

    let result = 1
    for (i', j') in valid neighbours of (i, j):
        if matrix[i'][j'] <= matrix[i][j]: continue
        result = max(result, 1 + DFS(matrix, memory, i', j'))

    memory[i][j] = result
    return result

The algorithm do looks simpler than the problem looks like.

The time complexity and space complexity are both O(MN) since the memory table will be filled only once.

Last

That’s it. CU next week :P