Sorting algorithm

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

Asymptotic notations

Bubble sort

Keep repeating the adjacent elements if they are in wrong order.

Algorithm

1. Scan array from left to right.
2. In every pass, bubble up the largest value to the end.

Following is the code to implement this algorithm.

const swap = (arr, i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}
const bubbleSort = (nums) => {
    const n = nums.length;
    for (let i=0; i < n; i++) {
        for (let j=n-1; j >i; j--) {
            if(nums[j] < nums[j-1]) {
                swap(nums, j, j-1);
            }
        }
    }
    
    return nums;
}

Time complexity: O(n*n)

Selection sort

Select the smallest element from unsorted portion of the list and move it to the sorted portion of the list.

Algorithm

1. Scan from left to right to find the next smallest element for index i .
2. Once find then swap it with ith position.

Following is the code to implement the selection sort.

const swap = (arr, i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}
const selectionSort = (nums) => {
    const n = nums.length;
    for (let i=0; i < n; i++) {
        let minIndex = i;
        for (let j=i+1; j < n; j++) {
            if(nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        // swap
        swap(nums, i, minIndex);  
    }
    return nums;
}

Time complexity: O(n*n)

Selection sort vs Bubble sort

Due to the similar nature of implementation, these two sorting algorithm sounds the same which cause confusion.

Following are similarities

1. Both sorting algorithm place ith sorted element on ith iteration.
2. Both are the brute force algorithm
3. Technically both algorithm selects ith sorted element on ith iteration, the only difference is how they discover it.
4. Both are in place algorithm.

Following are differences

1. Selection sort selects ith sorted element iterating from left to right.
2. Bubble sort bubble out ith sorted element iterating from right to left by comparing two elements.
3. Selection sort finds out ith sorted element and swap with the current ith element.
4. Bubble sort simply bubbles out the smallest element in each iteration. It has no relation to the current ith element.
5. Since bubble sort maintains the order of an element, therefore, it is stable sort compare to Selection sort which is an unstable sort.

Merge sort

• It is based on assumption that merging two sorted arrays are faster.
• It also assumes that array with single element is already sorted.
• This is not in place algorithm i.e. it needs additional storage to store merged sorted array and then copy back into original array
• This is recursive in nature

Following is the code to implement this.

const mergeSort = (nums, start, end) => {
    // base case: Size 1 is already sorted
    if(start >= end) {
        return;
    }
    // partition based on index
    const mid = start + Math.floor((end-start)/2);
    
    // sort left
    mergeSort(nums, start, mid);
    
    // sort right
    mergeSort(nums, mid + 1, end);
    
    // apply combine 
    let i=start;
    let j = mid + 1;
    const arr = [];
    while(i <= mid && j <= end) {
        if(nums[i] <= nums[j]) {
            arr.push(nums[i]);
            i++;
        } else {
            arr.push(nums[j]);
            j++;
        }
    }
    // copy leftover
    while(i <= mid) {
        arr.push(nums[i]);
        i++;
    }
    while(j <= end) {
        arr.push(nums[j]);
        j++;
    }
    // replace original arr
    for (let i=0; i < arr.length; i++) {
        nums[start+i] = arr[i];
    }
}
const sort  = nums => {
  mergeSort(nums,0, nums.length - 1);
}

Time complexity: O(n*nlogn)

493. Reverse Pairs

https://leetcode.com/problems/reverse-pairs/description/

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Example 1:

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Approach: Apply merge sort

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function (nums) {
    const n = nums.length;
    const mergeSort = (start, end) => {
        if (start >= end) {
            return 0;
        }
        const mid = start + Math.floor((end - start) / 2);
        let count = mergeSort(start, mid) + mergeSort(mid + 1, end);
        // ith num in [start, mid] and jth in [mid+1, end]
        let i = start;
        let j = mid + 1;
        while (i <= mid) {
            while (j <= end && nums[i] > 2 * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
            i++;
        }
        // sort
        merge(start, mid, end);
        return count;
    }
    const merge = (start, mid, end) => {
        const temp = [];
        let left = start;
        let right = mid + 1;
        while (left <= mid && right <= end) {
            if (nums[left] <= nums[right]) {
                temp.push(nums[left++]);
            } else {
                temp.push(nums[right++]);
            }
        }
        // copy leftover left
        while (left <= mid) {
            temp.push(nums[left++]);
        }
        // copy leftover right
        while (right <= end) {
            temp.push(nums[right++]);
        }
        // copy into original arr
        for (let i = 0; i < temp.length; i++) {
            nums[start + i] = temp[i];
        }
    }
    return mergeSort(0, n - 1);
};

Sort linked list using merge sort

https://leetcode.com/problems/sort-list/description/

Merge sort can be used to sort the linked list. Following are steps.

1. Write function to get middle node using slow/fast pointer approach
2. As a manager, split original list into two lists, left and middle.
3. Ask two workers to sort left and right list.
4. Use the two sorted list from worker and let manager to sort it

Following is the code to implement this algorithm.

const getMiddleNode = (head) => {
    let slow = head;
    let fast = head;
    let ans = slow;
    while(slow !== null && fast !== null && fast.next !== null ) {
        ans = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    return ans;
}
const mergeTwoSortedList = (left, right) => {
    const head = new ListNode();
    let node = head;
    while(left && right) {
        if(left.val <= right.val) {
            // Choose left
            node.next = left;
            left = left.next;
        } else {
            // Choose right
            node.next = right;
            right = right.next;
        }
        // Move next ptr
        node = node.next;
    }
    // Copy rest of the list
    node.next = left ? left: right;
    return head.next;
}
const mergeSort = (node) => {
    // Base case
    if(node == null || node.next == null) {
        return node;
    }
     // Find out middle node
     const middle = getMiddleNode(node);
     let left = node;
     let right = middle.next;
     middle.next = null; // Split into two list

     // Let worker to sort left and right list
     left = mergeSort(left);
     right = mergeSort(right);

     // Merge two sorted list
     return mergeTwoSortedList(left, right);
 }
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    return mergeSort(head);
};

External Merge sort

5GB of data in file on disk with 1GB RAM, how you can sort it?

Can’t load whole 5GB data into RAM therefore can’t apply standard algorithm.

1. You can load 1GB data and sort it.
2. But you can’t load next 1GB data and perform comparison to sort 2GB data.
3. If you keep loading sorted data from disk for comparison then it will take forever time using insertion sort

Can we leverage merge sort to solve this problem?

Step #1: Chunks as per RAM size and sort it

1. Break 5GB data into 1GB data of separate file
2. Load each file in RAM, sort it using any of the standard algorithm and then write into separate file on disk.

Step #2: Apply k-way merge on sorted files

1. Take 150MB data from each file and load into RAM
2. It will consume total of 750MB of RAM
3. It will have 250MB left on RAM
4. Perform 5 way merge on 5 array and keep writing into remaining 250MB left RAM.
5. K-way merge will fill sorted data from left to right. Once 250GB RAM is full then write it into disk and free up spaces.
6. Once any of the 5 merge pointer i reached to end then load next batch of 150MB of data from that file and reset pointer variable.
7. Keep doing it until file data is exhausted
8. Every time 250GB RAM get full and data is written on disk with separate file name.

External merged sort is used when data can’t be fit in memory.

Quick sort

It is based on partitioning array into following three parts

1. First part with all elements less than second part
2. Second part has all equal elements greater than first part
3. Third part has all elements greater than second part

Following are few important points

• This algorithm pick first element (or randomly pick element and swap with first one) as pivot and place it to its correct position.
• Then run recursion to solve the left and right sub array to sort it.
• There are three partitions algo

a. Lomuto partition — proceed from left to right in single direction

b. Tony Hore — Proceed from both direction until both pointers crossed each other.

c. Three way partitioning

Lomuto partition with both left pointers

1. Choose starting element as pivot=nums[start] and goal is to find the position of this element.
2. Start two pointers i=start+1 and j=start+1
3. i represents right boundary such that every elements from start....i-1 are less than the pivot . Remember, i doesn’t represent the last element less than pivot , instead it represents the boundary where all elements before this are lesser than pivot
4. We only increment j to scans each elements.
5. If find jth element lesser than pivot then swap ith with jth and increment i so that i will keep pointing to boundary.
6. At the end, we can place pivot to just before i . It means we can swap start (which represent pivot ) with i-1 to place pivot to it’s correct position.

const partitionLumuto = (nums, start, end) => {
    const pivot = nums[start];
    let i = start + 1;
    let j = start + 1;
    while(j <= end) {
        if(nums[j] <= pivot) {
            swap(nums, i, j);
            i++;
        }
        j++;
    }
    swap(nums, start, i-1);
    return i - 1;
}

Horare partition with left and right pointers

1. Choose pivot=nums[start]
2. Initialize i=start and j=end and keep processing both pointers till i<=j
3. ith represent the left boundary such that any elements between start....i-1 will be smaller than the pivot.
4. It means on scanning array if nums[i]<= pivot is found then simply increment i++ i.e. move to right.
5. jth represet the right boundary such that any elments between j....end will be larger than the pivot.
6. It means on scanning array if nums[j] > pivot is found then simply decrement j-- i.e. move to left.
7. If both condition are not satisfied that means jth is on violation stage, at this time we will swap ith and jth . At this moment no need to change any pointer. The top level while loop will take care of incrementing pointer next time.
8. At the end, swap pivot position with i-1 index to place the pivot at it’s correct position.

const partitionHorare = (nums, start, end) => {
    const pivot = nums[start];
    let i= start;
    let j= end;
    while(i <= j) {
        if(nums[i] <= pivot) {
            i++;           
        }
        else if (nums[j] > pivot) {
            j--
        } else {
            swap(nums , i, j);
        }
    }
    // put pivot on its right place
    swap(nums, start, i-1);
    return i-1;
}

Dijkastra partitioning with three pointers to place all equal pivot in one pass

1. Initialize pivot=nums[start]
2. Initialize left=start and right=end .
3. Initialize a third pointer let’s call it i=start
4. In this approach, we use third pointer to scan the array till i <= right
5. End goal is to place all duplicates of pivot to it’s correct position in one pass.
6. At the end left and right will point to the right position of pivot.
7. If nums[i] < pivot then swap it with left i.e. keep moving pivot value to left and increment both i and left .
8. If nums[i] > pivot then swap ith with right and only decrement right . Goal is to keep moving higher element to right side.
9. Else simply increment i . This only happens if element is same as pivot i.e. duplicate.
10. At the end, return [left, right] as partition boundary.

const partitionDijkastra = (nums, start, end) => {
    const pivot = nums[start];
    let left = start;
    let right = end;
    let i = start;
    while(i <=right) {
        if(nums[i] < pivot) {
            swap(nums, i, left);
            i++;
            left++;
        }
        else if (nums[i] > pivot) {
            swap(nums, i, right);
            right--;
        } else {
            i++;
        }
    }
    return [left, right];
}

Quick sort code

We can choose any of the partition algorithm and write the quick sort code as below using Lumto parition.

const partitionLumuto = (nums, start, end) => {
    const pivot = nums[start];
    let i = start + 1;
    let j = start + 1;
    while(j <= end) {
        if(nums[j] <= pivot) {
            swap(nums, i, j);
            i++;
        }
        j++;
    }
    swap(nums, start, i-1);
    return i - 1;
}
const quickSortLumuto = (nums, start, end) => {
    
    if(start >= end) {
        return;
    }
    const pIndex = partitionLumuto(nums, start, end);
    // sort left
    quickSortLumuto(nums, start, pIndex -1);
    // sort right
    quickSortLumuto(nums, pIndex + 1, end);
} 
const sort = nums => {
  quickSortLumuto(nums, 0, nums.length);
}

Quick select algorithm

Quick sort algorithm place pivot element to it’s own position. We don’t know what would be the position.

But we can modify Quick sort to place element on given kth positon to find out the kth position number in minimum partition instead of running the complete sorting algorithm.

1. Run partition algo to find pIndex
2. If pIndex == k then return nums[pIndex] as at this moment pivot must have placed on pIndex .
3. Otherwise check where does k lies.
4. Ie. if pIndex < k then we can only search the right window.
5. If pIndex >k then we can simply search the left window.

Following is Quick select code using Lumoto partition.

const partitionLumoto = (nums, start, end) => {
    const pivot = nums[start];
    let i = start + 1;
    for (let j= start + 1; j <= end; j++) {
        if(nums[j] <= pivot) {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, start, i -1);
    return i - 1;
}

const quickSelect = (nums, k, start, end) => {
    if(start > end) {
        return;
    }
    const targetIndex = nums.length - k;
    const pIndex = partitionLumoto(nums, start, end);
    if(pIndex === targetIndex) {
        return nums[pIndex];
    }
    if(pIndex < targetIndex) { // move right
       return quickSelect(nums, k, pIndex + 1, end); 
    }
    // move left
    return quickSelect(nums, k, start, pIndex - 1);
}

Counting sort

Count the frequency of each distinct element in the input array and use that information to place the elements in their correct sorted positions.

const sort = arr => {
    const n = arr.length;
    const max = Math.max(...arr);
    const count = new Array(max + 1).fill(0);

    // Phase 1: Initialize with frequency of each element
    for(const num of arr) {
        count[num]++;
    }
    // Phase 2: Calculate running sum for frequency
    for(let i=1; i < count.length; i++) {
        count[i] += count[i-1]
    }
    // Phase 3: Print number from right to left to keep sorting stable
    const result = new Array(n).fill(0);
    for(let i= n-1; i >=0; i--) {
        const num = arr[i]; // Scan original array
        const position = --count[num];
        result[position] = num;
    } 
    // Phase 3: For inplace, otherwise return result
    for(let i=0; i < n; i++) {
        arr[i] = result[i];
    }       
}

Radix sort

1. Find the largest element in the array, which is 802. It has three digits, so we will iterate three times, once for each significant place.
2. Sort the elements based on the unit place digits (X=0). We use a stable sorting technique, such as counting sort, to sort the digits at each significant place.

[170, 90, 802, 2, 24, 45, 75, 66].

3. Sort the elements based on the tens place digits.

[802, 2, 24, 45, 66, 170, 75, 90]

4. Sort the elements based on the hundreds place digits.

[2, 24, 45, 66, 75, 90, 170, 802]

The array is now sorted in ascending order.

const getDigit = (num, radix) => {
    // Here number system base is 10      
    return Math.floor(num/Math.pow(10, radix))%10;
}

const countingSort = (arr, radix = 0) => {  
    const n = arr.length; 
    // Initialize buckets bucket of size 10 for base 10 number
    const buckets = new Array(10).fill(0);    
    // Calculate the count of elements
   for (let i=0; i < n; i++) {
        const index = getDigit(arr[i], radix);
        buckets[index]++;
   }
   // Calculate cumulative sum to support stable sorting
   for (let i=1; i < buckets.length; i++) {
        buckets[i] += buckets[i-1];
   }
   // Place the element in sorted order printing from right to left
   const output = new Array(n).fill(0);
   for(let i=n -1; i >= 0; i--) {
        const digit = getDigit(arr[i], radix);
        const position = --buckets[digit];
        output[position] = arr[i];
   } 

   // Copy sorted output to original array
   for (let i=0; i < n; i++) {
        arr[i] = output[i];
   }
}
const numberOfDigits = (num) => {
    return Math.floor(Math.log10(num)) + 1;
}
const radixSort = (arr)=> {
    // Find max number to determine the number of digits
    const max = Math.max(...arr);
    const digits = numberOfDigits(max);
    for(let i=0; i< digits; i++) {
        countingSort(arr, i);
    }
}

Bucket sort

Let’s try to sort following array.

[0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

Create n empty buckets (Or lists) and do the following for every array element arr[i].

1. Insert arr[i] into bucket[n*array[i]]
2. Sort individual buckets using insertion sort.
3. Concatenate all sorted buckets.

const getBucket = ()=> {
    // Create bucket of size 10
    return new Array(10).fill(0).map(a => []);
}
const getBucketIndex = num => {
    return Math.floor(num * 10);
}
const bucketSort = arr => {
    const n = arr.length;
    // Get bucket
    const bucket = getBucket();

    // Scatter nums i.e. insert elements into their respective buckets
    for (let i=0; i < n; i++) {
        const num = arr[i];
        const index = getBucketIndex(num);   
        bucket[index].push(num);     
    }
    // Sort each bucket
    for (let i=0; i < bucket.length; i++) {
        bucket[i].sort((a,b) => a - b); // or write custom sort algorithm eg, inserstion sort in above step
    }
    // Gather buckets
    let k=0;
    for (let i=0; i < bucket.length;i++) {
        for (let j=0; j < bucket[i].length; j++) {
            arr[k++] = bucket[i][j];
        }
    }

}

Heap sort

Heap sort is a comparison-based sorting technique based on Binary Heap Data Structure. It can be seen as an optimization over selection sort where we first find the max (or min) element and swap it with the last (or first). We repeat the same process for the remaining elements.

In Heap Sort, we use Binary Heap so that we can quickly find and move the max element (In O(Log n) instead of O(n)) and hence achieve the O(n Log n) time complexity.

Following are steps

1. Represent array as complete binary tree

2. Transform the array into max heap:

To transform a heap into a max-heap, the parent node should always be greater than or equal to the child nodes.

3. Remove the maximum element in each step and move at the end

Following is code for reference.

const leftChild = i => i * 2 + 1;
const rightChild = i => i * 2 + 2;
const parentNode = i => Math.floor((i-1)/2);
const heapifyDown = (nums, end, i) => {
    const left = leftChild(i);
    const right = rightChild(i);
    let largest = i;
    if(left <= end && nums[left] > nums[largest]) {
        largest = left;
    }
    if(right <= end && nums[right] > nums[largest]) {
        largest = right;
    }
    // if changed
    if(largest !== i) {
        swap(nums, i, largest);
        heapifyDown(nums, end, largest);
    }
}
const removeTop = (nums, end) => {
    const top = nums[0];
    // swap with first and last
    swap(nums, 0, end);
    // heapify down the new top
    heapifyDown(nums, end, 0);
    return top;
}
const buidHeap = nums => {
    const n = nums.length;
    for(let i= Math.floor((n-1)/2); i >=0; i--) {
        // apply heapify down
        heapifyDown(nums, n, i);
    }
}
const heapSort = nums => {
    // build heap
    buidHeap(nums);

    // remove max iteratively
    for(let i=nums.length-1; i >= 0; i--) {
        removeTop(nums, i);
    }
}

Custom sorting

Some of the problems needs customized sorting. Let’s go through following.

406. Queue Reconstruction by Height

https://leetcode.com/problems/queue-reconstruction-by-height/description/

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Approach

Let’s consider given example people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

Use case #1 : When two person share same height

In this case, we can simply sort it based on k ascending order.

Note: One major thing to keep in mind here is that these people need not be right next to each other.

Note: If you put someone shorter in between them, neither of them will notice.

Note: If you were to put someone taller than them in between, the people behind this person must have a k value that accommodates them.

Use case#2: Insert taller between two same heights

In this case, we need to put someone taller in between these two individuals since the second person requires a 2nd person taller than him in front.

In fact, let’s introduce two new taller people:

The same rule applies to these two people;k values sorted in ascending order. Now, what happens if we combine them?

As you can see, the people who share the same heights maintain their relative order.

But now comes the question, how did we decide the order of people with different heights? Now is where things get a bit strange.

Tric:

We insert the tallest people into our output first. Then we insert the people of the next tallest height into the output using their k value as their index.

The reason this works is because people of taller heights don’t care about the positions of those who are shorter than them. So we can do this height-by-height.

After sorting: [ [ 7, 0 ], [ 7, 1 ], [ 6, 1 ], [ 5, 0 ], [ 5, 2 ], [ 4, 4 ] ]

Now build the output:

Just to be completely clear, this works because of two reasons:

1. Taller heights aren’t affected by shorter heights
2. We can sort each individual height in ascending order by k

Following is code for reference.

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function (people) {
    // Sort the input based on height
    people.sort((p1, p2) => {
        // Same height, sort by k
        if (p1[0] === p2[0]) {
            return p1[1] - p2[1];
        }
        // Different height, sort by height as descending order
        return -p1[0] + p2[0];
    });

    // Taller heights aren't affected by shorter heights. 
    // We insert the tallest people into our output first. 
    // Then we insert the people of the next tallest height into the output using their k value as their index.
    const ans = [];
    for (const person of people) {
        ans.splice(person[1], 0, person);
    }
    return ans;
};

658. Find K Closest Elements

https://leetcode.com/problems/find-k-closest-elements/description

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or
• |a - x| == |b - x| and a < b

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Approach 1: Sort With Custom Comparator

The comparator should be abs(x - num) for each num in arr . Following is code for reference.

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function (arr, k, x) {
    arr.sort((a, b) => Math.abs(a - x) < Math.abs(b - x));
    return arr.slice(0, k);
};

Approach 2: Binary Search + Sliding Window

TBD

539. Minimum Time Difference

https://leetcode.com/problems/minimum-time-difference/description

Given a list of 24-hour clock time points in “HH:MM” format, return the minimum minutes difference between any two time-points in the list.

Example 1:

Input: timePoints = ["23:59","00:00"]
Output: 1

Approach

1. Convert time into minutes scale. For example 23:59 will be come 23*60+59=1,439
2. Apply sorting based on converted value.
3. Compare every pair to find out the minimum difference.
4. But we do have edge case when smallest difference is between first and last element. For example if the last and first time is “22:00” and “02:00”, then the time difference is 240 minutes. But answer should be 0 minutes.
5. For edge case, we need to take the minimum of ans and 24*60 — (minutes[n-1] — minutes[0])

Following is code for reference.

/**
 * @param {string[]} timePoints
 * @return {number}
 */
var findMinDifference = function (timePoints) {
    const minutes = timePoints.map(a => {
        const [hh, mm] = a.split(':');
        return parseInt(hh) * 60 + parseInt(mm);
    });
    minutes.sort((a, b) => a - b);
    const n = minutes.length;
    let ans = Number.MAX_SAFE_INTEGER;
    for (let i = 1; i < n; i++) {
        ans = Math.min(ans, minutes[i] - minutes[i - 1]);
    }
    return Math.min(ans, 24*60  - (minutes[n-1] - minutes[0]));
};

B. Penchick and Satay Sticks

https://codeforces.com/contest/2031/problem/B

Penchick and his friend Kohane are touring Indonesia, and their next stop is in Surabaya!

In the bustling food stalls of Surabaya, Kohane bought 𝑛 satay sticks and arranged them in a line, with the 𝑖-th satay stick having length 𝑝𝑖. It is given that 𝑝 is a permutation∗ of length 𝑛.

Penchick wants to sort the satay sticks in increasing order of length, so that 𝑝𝑖=𝑖 for each 1≤𝑖≤𝑛. For fun, they created a rule: they can only swap neighboring satay sticks whose lengths differ by exactly 1. Formally, they can perform the following operation any number of times (including zero):

• Select an index 𝑖 (1≤𝑖≤𝑛−1) such that |𝑝𝑖+1−𝑝𝑖|=1;
• Swap 𝑝𝑖 and 𝑝𝑖+1.

Determine whether it is possible to sort the permutation 𝑝, thus the satay sticks, by performing the above operation.

∗∗A permutation of length 𝑛 is an array consisting of 𝑛 distinct integers from 1 to 𝑛 in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (𝑛=3 but there is 4 in the array).

Approach # 1: BFS graph traversal (TLE)

We can treat each input state and node and all possible moves as neighbor. The neighbor with sorted order gives the answer. If none is found as sorted order then return “NO”. Following is code for reference.

#include "bits/stdc++.h"
using namespace std; 

char SEP = '-';
string getNode(vector<int>& nums) {
    int n = nums.size();
    stringstream ss; 
    for(int i=0; i < n; i++) {
        int num = nums[i];
        if(i==0) {
            ss<<num;
        } else {
            ss<<SEP<<num;
        }
    }
    return ss.str();
}
vector<int> getNums(string node) {
    vector<int> nums; 
    stringstream ss(node); 
    string token;
    while(getline(ss, token, SEP)) {
        nums.push_back(stoi(token));
    }
    return nums;
}
bool isSorted(string node) { // increasing order 
    vector<int> nums = getNums(node);
    int n = nums.size();
    for(int i=0; i < n-1; i++) {
        if(nums[i] > nums[i+1]) {
            return false;
        }
    }
    return true;
}
void swap(vector<int> & nums, int i,int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
vector<string> getNeighbors(string node) {
    vector<int> nums = getNums(node);
    vector<string> neighbors;
    int n = nums.size();
    for(int i=0; i < n-1; i++) {
        if(abs(nums[i] - nums[i+1]) == 1) {
            swap(nums, i, i+1);
            neighbors.push_back(getNode(nums));
            swap(nums,i, i+1);
        }
    }    
    return neighbors; 
}
string solve(vector<int>& nums) {
    int n = nums.size();
    string start = getNode(nums);
    queue<string> q;
    q.push(start);
    unordered_set<string> visited = {start}; 
    while(!q.empty()) {
        string node = q.front();
        q.pop();
        if(isSorted(node)) {
            return "YES";
        }
        for(string neighbor : getNeighbors(node)) {
            if(visited.count(neighbor) == 0) {
                q.push(neighbor);
                visited.insert(neighbor);
            }
        }
    }
    
    return "NO";
}

int main()
{
    int t;
    cin >> t; 
    for (int i=0; i < t; i++) {
        int n; 
        cin >> n;
        vector<int> nums(n);
        for(int j=0; j < n; j++) {
            cin>>nums[j];
        }
        cout <<solve(nums)<<endl;
    }
    return 0;
}

Approach #2: Count the unordered pairs

Since as per constraints, input will always be permutation of [1…n] therefore we can simply count possible pair that can be swap to make input sorted. Following is code for reference.

#include "bits/stdc++.h"
using namespace std; 

void swap(vector<int> & nums, int i,int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
string solve(vector<int>& nums) {
    int n = nums.size();
    for(int i=1; i < n; i++) {
        if(nums[i]>= nums[i-1]) {
            continue;
        }
        if(abs(nums[i] - nums[i-1]) == 1) {
            swap(nums, i, i-1);
        } else {
            return "NO";
        }
    }
    
    return "YES";
}

int main()
{
    int t;
    cin >> t; 
    for (int i=0; i < t; i++) {
        int n; 
        cin >> n;
        vector<int> nums(n);
        for(int j=0; j < n; j++) {
            cin>>nums[j];
        }
        cout <<solve(nums)<<endl;
    }
    return 0;
}

Sort an almost sorted array where only two elements are swapped

Given an almost sorted array where only two elements are swapped, how to sort the array efficiently?

Example#1

Input:  arr[] = {10, 20, 60, 40, 50, 30}  
// 30 and 60 are swapped
Output: arr[] = {10, 20, 30, 40, 50, 60}

Approach# 1: Scan from right to left to find first mismatched then from left to right

void swap(vector<int>& nums, int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}
pair<int,int> mismatch(vector<int> & nums) {
    int n = nums.size();
    int first = -1;
    int second = -1;
    for(int i=n-1; i > 0; i--) {
        if(nums[i] < nums[i-1]) {
            first=i;
            int j =0;
            while(j < i) {
                if(nums[j] > nums[j+1]) {
                    second = j;
                    return make_pair(first, second);
                }
                j++;
            }
        }
    }
    return {};
}
void solve(vector<int>& nums) {
  auto[first, second] = mismatch(nums);
  swap(nums, first, second);
}

Happy sorting :-)