O(1) Space or in-place

Some problems require O(1) space. I’d like to summary some of this kind of question here.

442. Find All Duplicates in an Array

Basis idea

Since we can only have the number from 1 to n. We can use the index to save the information about whether this number is visited or not.

The negative sign will indicate that the number is visited before. At the same time, the original value is kept by taking the abs(num[i]) operation.

If num[i] is less than 0, it means the number (i+1) is visited one time. If we visit number i+1 and find num[i] is negative, it means this is the second time that we are visiting number i+1, it is one of the correct results.

Code

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for num in nums:
            # second time to look the number, append it to res.
            if nums[abs(num)-1]<0:
                res.append(abs(num))
            else:# first time look this number, set the related location to negative
                nums[abs(num)-1] *=-1
        return res

Take away

For O(1) space problem, we can either use strict O(1) space or taking the benefit of reuse some space from the data structure itself such as nums here. A commonly used trick is to use the index information of the array of lists.

We can also solve it by adding an extra bit in the left-most position

const int extra_bit = 1<<30;
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ret;
        for (auto n : nums)
        {
            auto clean_n = n & (~extra_bit);
            if (nums[clean_n-1] & extra_bit) ret.push_back(clean_n);
            else nums[clean_n-1] |= extra_bit;
        }
        return ret;
    }
};

234. Palindrome Linked List

73. Set Matrix Zeroes

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rows , cols = set(), set()
        if not matrix or not matrix[0]:return
        R, C = len(matrix), len(matrix[0])
        for i in range(R):
            for j in range(C):
                if not matrix[i][j]:
                    rows.add(i)
                    cols.add(j)
        for i in rows:
            for j in range(C):
                matrix[i][j] = 0
       
        for j in cols:
            for i in range(R):
                matrix[i][j] = 0

31. Next Permutation

289. Game of Life

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:return
        # will_die = -1, will_born = 2
        R, C = len(board), len(board[0])
        def live_neighbor(i,j):
            if i<0 or i>=R or j<0 or j>=C:return 0
            return abs(board[i][j])==1
        def number_neighbors(i,j):
            return sum(live_neighbor(i+di, j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)])
        for i in range(R):
            for j in range(C):
                n = number_neighbors(i,j)
                # current live
                if board[i][j]:
                    if n<2:board[i][j] = -1
                    elif n>3:board[i][j] = -1
                else:
                    if n==3:board[i][j] = 2
        for i in range(R):
            for j in range(C):
                if board[i][j]==2:
                    board[i][j] = 1
                elif board[i][j] == -1:
                    board[i][j] = 0

Or using bit manpipulation to save the new result in the second bit.

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:return
        # will_die = -1, will_born = 2
        R, C = len(board), len(board[0])
        def live_neighbor(i,j):
            if i<0 or i>=R or j<0 or j>=C:return 0
            return board[i][j]&1
        def number_neighbors(i,j):
            return sum(live_neighbor(i+di, j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)])
        for i in range(R):
            for j in range(C):
                n = number_neighbors(i,j)
                # current live
                if board[i][j]:
                    if 2<=n<=3:board[i][j] |= 2
                else:
                    if n==3:board[i][j] |= 2
        for i in range(R):
            for j in range(C):
                board[i][j]>>=1