Guidelines

The category is named Arrays but it actually contains hints on how to work with many container types. Below are few tips/cheatsheet to remember while tackling array problems:

• Always ask about the nature of elements in the input array (positive, negative, sorted, min, max...)
• Use Writer and Iterator combination to discard/keep elements nums[writer++] = nums[i]
• For storing info on array elements use hashmap/set
• Try sorting the array and see if it helps with the problem
• Missing number think about XOR
• Reuse the array for marking existince of elements removing the need for additional storage by using nums[(nums[i]-1)%n] += n; or nums[Math.abs(nums[i]) - 1] *= -1 tricks
• To flat the matrix use following tranformation int row = i / n, column = i % n;
• right-shift operator >>> since the >> carries over the value of most significant bits (which will then not work for negative number),
• Use n&1 to extract last bit, and result |= (n & 1) << mask to set bit at position mask
• If there is a matching defined by the problem statement (e.g. ( and )) use stack
• use int[][] directions = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1}}; for spiral matrix traversing
• PrefixSum prefixSum[i] = nums[0] + nums[1] + nums[2] + ... + nums[i-1] sum between i and j (prefixSum[j+1]-prefixSum[i-1] if elements at i and j are included)
• Remember you can have custom hashing function (Group Anagrams)
• Union find

Java

private int findParent(int[] parent, int idx){
    if(parent[idx] == -1) return idx;
    return findParent(parent, parent[idx]);
}

private void union(int parent[], int x, int y)
{
    int xset = findParent(parent, x);
    int yset = findParent(parent, y);
    parent[xset] = yset;
}

JavaScript

function findParent(parent, idx) {
  if (parent[idx] === -1) return idx;
  return findParent(parent, parent[idx]);
}

function union(parent, x, y) {
  const xset = findParent(parent, x);
  const yset = findParent(parent, y);
  parent[xset] = yset;
}

Python

def findParent(parent, idx):
    if parent[idx] == -1:
        return idx
    return findParent(parent, parent[idx])

def union(parent, x, y):
    xset = findParent(parent, x)
    yset = findParent(parent, y)
    parent[xset] = yset

C++

int findParent(vector<int>& parent, int idx) {
    if (parent[idx] == -1)
        return idx;
    return findParent(parent, parent[idx]);
}

void unionSet(vector<int>& parent, int x, int y) {
    int xset = findParent(parent, x);
    int yset = findParent(parent, y);
    parent[xset] = yset;
}

• Monotonic queue for selecting elements to discard Daily Temperatures and Largest Rectangle in Histogram