Competitive Coding : Standard Alogorithms

Sorting:

https://leetcode.com/problems/sort-an-array/

Quick Sort:

Divide and Conquer Algorithm.

In-Place Sorting Algorithm (No extra auxilary space needed)

It picks an element as pivot and partitions the given array around the picked pivot.

The optimised Partition() always tries to divide the partition in two equal halfes.

function swap(A,i,j){
    const temp=A[j];
    A[j]=A[i];
    A[i]=temp;
}

function getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

/**
 * This method is completely optional to call
 * It will be extemely useful when the array is sorted(Worst Case Complexity) 
 */

function optimise(A,indexLow,indexHigh,pivotIndex){
    const randomIndex=getRandomInt(indexLow,indexHigh);
    swap(A,randomIndex,pivotIndex);
}

/**
* This method partitions the array around the pivot element in such a way that all the elements smaller than the pivot are towards the left of pivot and elements greater than pivot are towards the right.
*
* @return {number} pivotIndex
**/
function partition(A,indexLow,indexHigh){
    
    /*
    The leftmost index is taken as the pivotIndex and all the elements on its left are always smaller than pivot.
    */
    let pivotIndex=indexLow;
    
    optimise(A,indexLow,indexHigh,pivotIndex);
    
    const pivot= A[pivotIndex];
    
    /*start from right untill we have reached the pivotIndex,
    all the elements on the right of j are always greater than pivot
    */
    let j=indexHigh;
    
    while(pivotIndex<j){
        
        if(A[j]<pivot){
            
            //shift it leftwards of pivot
            
            A[pivotIndex]=A[j];
            A[j]=A[pivotIndex+1];
            A[pivotIndex+1]=pivot;
            pivotIndex++;           
        }
        else{
            //only decrement j when it is greater than pivot
            --j;
        }
    }
   
    return pivotIndex;
}

function quickSortR(A,indexLow,indexHigh){
    
    if(indexLow>=indexHigh){
        return;
    }
    
    const pivotIndex=partition(A,indexLow,indexHigh);
    
    quickSortR(A,indexLow,pivotIndex-1);
    
    quickSortR(A,pivotIndex+1,indexHigh);
}


/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    quickSortR(nums,0,nums.length-1);
    return nums;
};

Time Complexity

Best Case : O(NLogN) The best case occurs when the partition process always picks the middle element as pivot.

Worst Case : O(N^2) The worst case occurs when the partition process always picks smallest/largest as pivot.Use the optimise() method to avoid it.

Avg Case : O(NLogN) The worst case occurs when the partition process always picks smallest/largest as pivot.Use the optimise() method to avoid it.

---

Merge Sort:

Divide and Conquer Algorithm.

Not a In-Place Sorting Algorithm.

It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

function mergeTwoSortedArray(A,start1,end1,start2,end2){
    
    const arr1=[];
    const arr2=[];
    for(let i=start1;i<=end1;i++){
        arr1.push(A[i]);
    }
    
     for(let i=start2;i<=end2;i++){
        arr2.push(A[i]);
    }
    
    let resultIndex=start1;
    
    let i=0;
    let j=0;
    
    while(resultIndex<=end2){
        if(i<arr1.length && j<arr2.length){
            //both in range
            if(arr1[i]<arr2[j]){
                A[resultIndex++]=arr1[i++];
            }
            else{
                A[resultIndex++]=arr2[j++];
            }
        }
        else{
            if(i<arr1.length){
                A[resultIndex++]=arr1[i++];
            }
            else{
                A[resultIndex++]=arr2[j++];
            }
        }
    }
}

function mergeSortR(A,startIndex,endIndex){
    
    if(startIndex==endIndex){
        return;
    }
    
    //keep dividing the array into two parts
    
    const mid=Math.floor((startIndex+endIndex)/2);
    
    mergeSortR(A,startIndex,mid);
    
    mergeSortR(A,mid+1,endIndex);
    
    mergeTwoSortedArray(A,startIndex,mid,mid+1,endIndex);
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    
    mergeSortR(nums,0,nums.length-1);
    
    return nums;
};

Time Complexity

Time complexity of Merge Sort is O(NLogN) in all 3 cases (worst, average and best) as merge sort always divides the array into two halves and takes linear time to merge two halves.

Space Complexity : O(N)

Applications:

1. Sorting of Linked List: Because we can insert items in the middle in O(1) extra space and O(1) time. Therefore, the merge operation of merge sort can be implemented without extra space for linked lists.
2. External Sorting: External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory, usually a hard disk drive.
3. Inversion Count Problem

---

Heap Sort and Binary Heap:

Based on Binary Heap data structure.

A Binary Heap is a Complete Binary Tree where items are stored in a special order such that the value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called max heap and the latter is called min-heap. The heap can be represented by a binary tree or array. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Since a Binary Heap is a Complete Binary Tree, it can be easily represented as an array and the array-based representation is space-efficient. If the parent node is stored at index I, the left child can be calculated by 2 * I + 1 and the right child by 2 * I + 2 (assuming the indexing starts at 0).

In-Place Sorting Algorithm,no auxilary memory is needed.

function swap(A,i,j){
    const temp=A[i];
    A[i]=A[j];
    A[j]=temp;
}


class MaxHeap {
  constructor(inputArr = null) {
    if (inputArr) {
      this.arr = inputArr;
      this.lastIndex = this.arr.length - 1;
      MaxHeap.buildHeap(this.arr);
    } else {
      this.arr = [];
      this.lastIndex = -1;
    }
  }

  /**
   * Restructure the array to form a heap
   * Time Compexity : Looks like it is O(NLogN) but it is O(N) and analysis is difficult to understand
   *
   **/
  static buildHeap(arr) {
    const N = arr.length;

    const lastNonLeafNode = Math.floor((N - 1) / 2);

    /* Way1
    Using HeapifyDown
    Guranteed O(N)
    */
    for (let i = lastNonLeafNode; i >= 0; i--) {
      MaxHeap.heapifyDown(arr, i, N);
    }

    /* Way2
    Using HeapifyUp
    O(NLogN)
    */
    // for (let i = 0; i < N; i++) {
    //   MaxHeap.heapifyUp(arr, i);
    // }
  }

  /**
   * Only call this method if all the above subtrees are heapified
   * Time Compexity: O(logN)
   *
   */
  static heapifyUp(A, index) {
    const parentIndex = Math.floor((index - 1) / 2);

    if (parentIndex < 0) {
      return;
    }

    if (A[parentIndex] < A[index]) {
      swap(A, parentIndex, index);

      MaxHeap.heapifyUp(A, parentIndex);
    }
  }

  /**
   *  Only call this method if all the below subtrees are heapified
   *
   * Time Compexity: O(logN)
   */
  static heapifyDown(A, index, N) {
    let child1 = 2 * index + 1;
    const child2 = 2 * index + 2;

    let maxIndex = index;

    if (child1 < N && A[child1] > A[maxIndex]) {
      maxIndex = child1;
    }

    if (child2 < N && A[child2] > A[maxIndex]) {
      maxIndex = child2;
    }

    if (maxIndex === index) {
      return;
    }

    swap(A, maxIndex, index);

    MaxHeap.heapifyDown(A, maxIndex, N);
  }

  /**
   * @param {number} x : number to insert in heap
   * O(LogN)
   */
  insert(x) {
    this.lastIndex++;
    this.arr[this.lastIndex] = x;

    MaxHeap.heapifyUp(this.arr, this.lastIndex);
  }

  /**
   * @param {number} indexToRemove : indexToRemove from heap
   * O(LogN)
   */
  removeIndex(indexToRemove) {
    //take this number to the root
    this.arr[indexToRemove] = Number.MAX_SAFE_INTEGER;
    MaxHeap.heapifyUp(this.arr, indexToRemove);

    //remove the root
    swap(this.arr, 0, this.lastIndex);
    this.lastIndex--;

    MaxHeap.heapifyDown(this.arr, 0, this.lastIndex + 1);
  }
}


/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    
    MaxHeap.buildHeap(nums);

    let index=nums.length-1;
    while(index>0){
        swap(nums,0,index);
        index--;
        MaxHeap.heapifyDown(nums,0,index+1);
    }
    
    return nums;
};

Time Complexity

Time complexity of Heap Sort is O(NLogN) and Time Complexity of buildHeap is O(N)

Space Complexity : O(1)

Applications of Heap Data Structure:

1. Priority Queues: Priority Queue is a logical representation of Binary Heap.
2. Kth Largest or Smallest Element.
3. Sort a nearly sorted (or K sorted) array

---

Topological Sort (DFS):

Only for Directed Acyclic Graph (DAG)

DFS Traversal

In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of the stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in the stack.

There can be multiple correct order

Following are the dependencies of the tools/packages/services:

What will be order in which we can install these dependencies ?

One Possible Solution can be

[ 'nodejs', 'npm', 'pm2', 'git', 'rabbitMq', 'apiService', 'efs', 'csvService' ]

https://leetcode.com/problems/course-schedule-ii/

function R(graph,currentNode,resultStack,stateMap){
    
    stateMap.set(currentNode,"PENDING");
    
    const neighbourList=graph.get(currentNode);
    
    for(let neighbour of neighbourList){
        
         if(stateMap.get(neighbour)==="PENDING"){
            //cyclic 
            return null;
        }
        
        if(stateMap.get(neighbour)!=="DONE"){
            if(!R(graph,neighbour,resultStack,stateMap)){
                return null;
            }
        }
    }
    
    stateMap.set(currentNode,"DONE");
    resultStack.push(currentNode);
    
    return resultStack;
}


function topologicalSort(graph){
    
    const resultStack=[];
    const stateMap=new Map();
    
    for(let [node,neighbours] of graph){
        stateMap.set(node,"NOT_VISITED");
    }
    
    let isCycle=false;
    for(let [node,neighbours] of graph){
        
        if(stateMap.get(node)=="NOT_VISITED"){
            
            let r =R(graph,node,resultStack,stateMap);
            if(!r){
                return [];
            }
        }   
    }
    
    return resultStack;
}

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
    
    return main();
    
    const graph= new Map();
    for(let i=0;i<numCourses;i++){
        graph.set(i,[]);
    }
    
    for(const relation of prerequisites){
        const from=relation[0];
        const to=relation[1];
        graph.get(from).push(to);
    }
    
    return topologicalSort(graph);
    
};

Time Complexity : O(V+E). The above algorithm is simply DFS with an extra stack.

Space Complexity : O(V)

Applications:

Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs.

---

Topological Sort (BFS) OR Kahn's Algorithm:

Only for Directed Acyclic Graph (DAG)

BFS Traversal

We calculate the indegree of all the vertexes and keep pushing vertexes in the queue when its in-degree = 0.

There can be multiple correct order possible.

Algorithm

1. Compute in-degree of all the vertex
2. Pick all the vertex with in degree as 0 and push them to Queue.
3. Remove a vertex from Queue , add it the result,decrement the in-degree of all its neighbour and if the in-degree of the neighbour is reduced to 0,push it in the queue
4. Repeat Step 3 untill Queue is empty
5. if result.length !== vertexes then graph is Cyclic

https://leetcode.com/problems/course-schedule-ii/

class MyQueue{
    
    constructor(){
        this.arr=[];
        this.start=-1;
        this.end=-1;
        this.length=0;
    }
    
    push(x){
        
        this.arr[++this.end]=x;
        
        if(this.start==-1){
            this.start=0;
        }
        this.length++;
    }
    
    isEmpty(){
        return this.length===0;
    }
    
    pop(){
        this.length--;
        
        return this.arr[this.start++];
    }
    
}


function topologicalSort(graph){
    
    const result=[];
    const inDegreeMap=new Map();
    
    for(let [node,neighbours] of graph){
        inDegreeMap.set(node,0);
    }
    
    for(let [node,neighbours] of graph){
        
        for(let neighbour of neighbours){
            inDegreeMap.set(neighbour,inDegreeMap.get(neighbour)+1);
        }
    }
    
    const q= new MyQueue();
    
    for(let [node,indegree] of inDegreeMap){
        if(indegree===0){
            q.push(node);
        }
    }
    
    while(!q.isEmpty()){
        
        const currentNode=q.pop();
        result.push(currentNode);
        
        const neighbourList=graph.get(currentNode);
        
        for(let neighbour of neighbourList){
            
            inDegreeMap.set(neighbour,inDegreeMap.get(neighbour)-1);
            
            if(inDegreeMap.get(neighbour)==0){
                q.push(neighbour);
            }
        }
    }
    
    if(result.length!==graph.size){
        //cyclic graph
        
        return [];
    }
    
    result.reverse();
    return result;
}

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
    
    const graph= new Map();
    for(let i=0;i<numCourses;i++){
        graph.set(i,[]);
    }
    
    for(const relation of prerequisites){
        const from=relation[0];
        const to=relation[1];
        graph.get(from).push(to);
    }
    
    return topologicalSort(graph);
    
};

Time Complexity : O(V+E).

Space Complexity : O(V) The extra space is needed for the Queue.

Try LongestIncreasingPathInMatrix problem with BFS.

---