Array Problems

QuickSort

void quicksort(int arr[], int low, int high) {
    if(low >= high) return;
    int pivot = arr[high], i = low;
    for(int j = low; j < high; j++) {
        if(arr[j] < pivot) swap(arr[i++], arr[j]);
    }
    swap(arr[i], arr[high]);
    quicksort(arr, low, i - 1);
    quicksort(arr, i + 1, high);
}

Kth Largest Element

int kthLargest(vector<int>& arr, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int num : arr) {
        pq.push(num);
        if(pq.size() > k) pq.pop();
    }
    return pq.top();
}

Rotate NxN Matrix 90°

void rotate(vector<vector<int>>& mat) {
    int n = mat.size();
    for(int i = 0; i < n; i++)
        for(int j = i; j < n; j++)
            swap(mat[i][j], mat[j][i]);
    for(int i = 0; i < n; i++)
        reverse(mat[i].begin(), mat[i].end());
}

Set Matrix Zeroes

Brute Force

Main Function

vector<vector<int>> zeroMatrix(vector<vector<int>> &matrix, int n, int m) {

    // Set -1 for rows and cols
    // that contains 0. Don't mark any 0 as -1:

  // TC: Traverse:O(n*m) x (markRow: O(m) + markColO(n))
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 0) {
                markRow(matrix, n, m, i);
                markCol(matrix, n, m, j);
            }
        }
    }

    // Finally, mark all -1 as 0:
    // TC : Traverse: O(n*m)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == -1) {
                matrix[i][j] = 0;
            }
        }
    }

    return matrix;
}

Helping Function

// TC: markRow: O(m)
void markRow(vector<vector<int>> &matrix, int n, int m, int i) {
    // set all non-zero elements as -1 in the row i:
    for (int j = 0; j < m; j++) {
        if (matrix[i][j] != 0) {
            matrix[i][j] = -1;
        }
    }
}

// TC: marCol:O(n)
void markCol(vector<vector<int>> &matrix, int n, int m, int j) {
    // set all non-zero elements as -1 in the col j:
    for (int i = 0; i < n; i++) {
        if (matrix[i][j] != 0) {
            matrix[i][j] = -1;
        }
    }
}

TC : O(n * m )(n + m) + O(n + m)

Better Approach

vector<vector<int>> zeroMatrix(vector<vector<int>> &matrix, int n, int m) {

  // SC : O (n + m)
    int row[n] = {0}; // row array
    int col[m] = {0}; // col array

    // Traverse the matrix:
    // TC : O(n*m)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 0) {
                // mark ith index of row wih 1:
                row[i] = 1;

                // mark jth index of col wih 1:
                col[j] = 1;
            }
        }
    }

    // Finally, mark all (i, j) as 0
    // if row[i] or col[j] is marked with 1.

  // RC: O(n*m)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (row[i] || col[j]) {
                matrix[i][j] = 0;
            }
        }
    }
    return matrix;
}

TC : 2 * (n * m) , SC: O(n + m)

Optimal

vector<vector<int>> zeroMatrix(vector<vector<int>> &matrix, int n, int m) {

    // int row[n] = {0}; --> matrix[..][0]
    // int col[m] = {0}; --> matrix[0][..]
  // col0 -> matrix[0][0]
  int col0 = 1;

    // step 1: Traverse the matrix and
    // mark 1st row & col accordingly:
  // TC:O(n*m)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 0) {
                // mark i-th row:
                matrix[i][0] = 0;

                // mark j-th column:
                if (j != 0)
                    matrix[0][j] = 0;
                else
                    col0 = 0;
            }
        }
    }

    // Step 2: Mark with 0 from (1,1) to (n-1, m-1):
    // TC:O(n*m)
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (matrix[i][j] != 0) {
                // check for col & row:
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    //step 3: Finally mark the 1st col & then 1st row:

  // mark the  0th row
  // O(m)
    if (matrix[0][0] == 0) {
        for (int j = 0; j < m; j++) {
            matrix[0][j] = 0;
        }
    }

  // mark the 0th col
  // O(n)
    if (col0 == 0) {
        for (int i = 0; i < n; i++) {
            matrix[i][0] = 0;
        }
    }

    return matrix;
}

TC : 2 * O((n-1) * (m-1)) + O(n) + O(m) -> 2 * O(n* m) , SC : O(1)