Cycle sort coding pattern

Chapter#1: Cycle Sort Standard algorithm

Cycle sort is categorized as decrease and conquer algorithm.

Compared to Selection sort, instead of focusing on leftmost spot and figure out which number goes there, in Cycle sort, we focus on leftmost number and figure out which spot it can go to (send it there via swap).

Let’s understand the Cycle sort using following example.

1. Start scanning from left to right.
2. For the given number 17 , let’s find out the right position.
3. We can find the right position by scanning all the number and count numbers less than or equal to 17 , we found x = (8)
4. Then the right position of 17 will be x-1 = 7
5. Swap it with left most.

6. Now the leftmost number is 9, let’s solve it using similar approach.

7. Count the numbers less than or equal 9 are x=5

8. Right position of 9 will be x-1=4

9. Now the leftmost number is 1 , let’s solve it using similar approach

10. Count the numbers less than or equal 1 are x=1

11. Right position of 1 will be x-1=0 which is same as current position.

12. It means we solved the left most position i=0 , and now we need to solve for the rest i.e. i=1

13. Repeat same.

Why it is called cycle sort?

If you see carefully, above process makes a cycle to rotate the unsorted numbers. This is the reason it is called cycle sort.

Following is sample code for reference to implement Cycle sort.

int getRank(vector<int>& nums, int num) {
    int n = nums.size();
    int rank = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] <= num) {
            rank++;
        }
    }
    return rank;
}
void cycleSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int rank = -1;
        // Note: for loop is used to avoid calling getRank() twice if use while loop
        for (; (rank = getRank(nums, nums[i]));) {
            if (i == rank - 1) {
                break;
            }
            swap(nums[i], nums[rank - 1]);
        }
    }
}

Note: We assume that there are no duplicates.

Time complexity

• O(n²)

Note: This pattern of Cycle sort is not generally used to solve the coding problem.

Chapter#2: Cycle Sort with boundary constraints

Let’s assume that we have given array of size n which contains unique number from 1 to n. How can we sort it?

With above constraints, it become clear that we can optimize getRank() method as below

int getRank(vector<int>& nums, int num) {
    return num;
}

It means, we can optimize cycle sort code as below.

void cycleSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (i != nums[i]-1) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
}

Time complexity

• O(2*n) ~ O(n)

This pattern is useful to solve various coding problems. Let’s solve few.

268. Missing Number

https://leetcode.com/problems/missing-number/description/

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8

Explanation:

n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Approach#1: Using cycle sort

1. If the size of array is n+1 then numbers in the range [0,n] would be sorted as below.

[0,1,2,3,4] n = 4

2. But in our case, the size of array is n but numbers are in the range of 0,….n therefore one number will not be able to get any spot in the array. This will be the missing number.

[0,1,2,3] n = 4, missing is 4

3. But there is a problem, number n if exist, will not be stored on the same index n as size of array is n therefore max index we can have is n-1 .

4. It means, in normal cycle sort, while(nums[i] !=i) will lead to infinite loop.

5. We will need a sanity check to handle the infinite loop as below

while (nums[i] != i) { // if not on the right index then swap it
    int d = nums[i]; // destination
    if (d != n) {  // swap only when within the boundary
        swap(nums[i], nums[d]);
    } else {
        break; // if outside of boundary i.e. number n exist then exit from loop
    }
}

6. In case number n exist, it will take the missing number spot.

Following is code for reference.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            while (nums[i] != i) {
                int d = nums[i];
                if (d != n) {
                    swap(nums[i], nums[d]);
                } else {
                    break;
                }
            }
        }
        // find missing
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return n;
    }
};

448. Find All Numbers Disappeared in an Array

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Approach#1: Using cycle sort

1. nums is size of n and stores integers in the range of 1...n
2. In sorted form it can be stored as below.

[1,2,3,4]

3. It means to store num we need to use num-1 index

4. Following is trace to apply cycle sort which will help to understand the boundary condition

 0 1 2 3 4 5 6 7
[4,3,2,7,8,2,3,1] i=0
[7,3,2,4,8,2,3,1] i=0
[3,3,2,4,8,2,7,1] i=0
[2,3,3,4,8,2,7,1] i=0
[3,2,3,4,8,2,7,1] i=0
[3,2,3,4,8,2,7,1] i=0 -> This lead to infinite loop, to handle it, we can skip
[3,2,3,4,8,2,7,1] i=1 -> do nothing, move to next i
[3,2,3,4,8,2,7,1] i=2, already at right position, move next
[3,2,3,4,8,2,7,1] i=3, already at right position, move next
[3,2,3,4,8,2,7,1] i=4, already at right position, move next
[3,2,3,4,1,2,7,8] i=4, already at right position, move next
[1,2,3,4,3,2,7,8] i=4, same as target so move to next

5. It means, if nums[i]-1 ==i then we can skip it.

Following is code for reference.

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        for (int i=0; i < n; i++) {
            while(nums[i] -1 != i) {
                int d = nums[i] -1;
                if(nums[d] == nums[i]) { // if destination already have same number then skip
                    break;
                }
                // swap
                swap(nums[i], nums[d]);
            }
        }
        for(int i=0; i < n; i++) {
            if(nums[i] - 1 != i) {
                ans.push_back(i+1); // expected number is index + 1
            }
        }
        return ans;
    }
};

287. Find the Duplicate Number

https://leetcode.com/problems/find-the-duplicate-number/description/

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2] # n=4 so that it has n+1=5 integers
Output: 2

Approach#1: Using cycle sort

1. We can only solve this problem using Cycle sort if we agreed to modify the array.
2. nums contains n+1 integers it means size of numsis n-1 contains numbers in the range of 1...n
3. If we rewrite it as per n equal to size of nums then it will contains n integers in the range of 1...n-1
4. It means, in the sorted ideal position, each num should be placed at num-1 position.

Following is code for reference.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        for (int i=0; i < n; i++) {
            while(nums[i]-1 != i) {
                int d = nums[i]-1;
                // break if target has same value
                if(nums[d] == nums[i]) {
                    break;
                }
                swap(nums[i], nums[d]);
            }
        }
        // find the repeated number placed at conflict position
        for(int i=0; i < n; i++) {
            if(nums[i]-1 != i) {
                return nums[i];
            }
        }
        return -1;
    }
};

645. Set Mismatch

https://leetcode.com/problems/set-mismatch/description/

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Approach: Using cyclic sort

We can apply cyclic sort similar to previous problem. A slight modification is required here to return both missing number and repeated number. Following is code for reference.

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        for(int i=0; i < n; i++) {
            while(nums[i]-1 != i) {
                int d = nums[i] -1;
                if(nums[d] == nums[i]) {
                    break;
                }
                swap(nums[i], nums[d]);
            }
        }
        for(int i=0; i < n; i++) {
            if(nums[i]-1 != i) {
                return {nums[i], i+1};
            }
        }
        return {};
    }
};

442. Find All Duplicates in an Array

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store the output

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Approach# Using cyclic sort

We can apply cyclic sort similar to before with difference of collecting all the duplicates.

Following is code for reference.

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            while (nums[i] - 1 != i) {
                int d = nums[i] - 1;
                if (nums[d] == nums[i]) {
                    break;
                }
                swap(nums[d], nums[i]);
            }
        }
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (nums[i] - 1 != i) {
                ans.push_back(nums[i]);
            }
        }
        return ans;
    }
};

41. First Missing Positive

https://leetcode.com/problems/first-missing-positive/description/

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Approach 1: using cyclic sort with partition

1. The minimum possible answer is 1
2. It means all the negative number (including zero) are irrelevant and can be ignored.
3. It means we can first apply partition to move all the negative number (including zero) can be moved to one partition and rest on the second.

Q. What would be largest missing positive number?

Could it be INT_MAX? No. The reason is, if array size is n then max missing positive number will be n+1 bcz we need to place number as below.

1 2 3 . . . n
# Smallest missing could be 1
# Largest missing could be n+1

Can we rewrite problem statement?

Given an unsorted integer array find the smallest missing integer number in the range of 1 to n+1

Following is code for reference

class Solution {
private:
    int partition(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j] <= 0) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        return i - 1;
    }

public:
    int firstMissingPositive(vector<int>& nums) {
        long p = partition(nums);
        long n = nums.size();
        for (long i = p + 1; i < n; i++) {
            while (nums[i] != i - p) {
                long d = nums[i] + p;
                if (d >= 0 && d < n && nums[i] != nums[d]) {
                    swap(nums[i], nums[d]);
                } else {
                    break;
                }
            }
        }
        long value = 1;
        for(long i=p+1; i < n; i++) {
            if(nums[i] == value) {
                value++;
                continue;
            }
            return value;
        }
        return value;
    }
};

765. Couples Holding Hands

https://leetcode.com/problems/couples-holding-hands/description/

There are n couples sitting in 2n seats arranged in a row and want to hold hands.

The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the ith seat. The couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2n - 2, 2n - 1).

Return the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

Example 1:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Let’s try following approach

1. Instead of thinking individual seat, let’s assume that we have a sofa of two seats. It means at sofa[i] we have two seats chair[2*i] and chair[2*i+1]
2. On sofa with two seat, we can assume that first seat i.e. chair[2*i]is correctly assigned. We only need to fix the second seat chair[2*i+1]with swap.
3. But how?
4. One approach is, find out the other pair of pair=otherPair(chair[2*i+1]) location in the chair[] and swap it.
5. This will correctly placed the couple. Now chair[2*i+1] will have new person and we need to repeat same.

Above algorithm resemble the cycle sort. We can code as below to implement it.

class Solution {
private:
    int getPartner(int i) { return i % 2 == 0 ? i + 1 : i - 1; }
    bool onSideBySide(int p1, int p2) {
        // p1 is fixed
        int p1Partner = getPartner(p1);
        return p2 == p1Partner;
    }
    int getSwapPosition(int k) {
        // Get the sofa index
        int sofa = k / 2;
        // on sofa, first position is always fixed
        int i = sofa * 2;
        int j = sofa * 2 + 1;
        if (k == i) { // if k is on first position
            return j; // return second position to swap
        }
        return i; // return first position to swap
    }

public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        int sofas = n / 2;
        unordered_map<int, int> map;
        for (int i = 0; i < n; i++) {
            map[row[i]] = i;
        }
        int ans = 0;
        for (int sofa = 0; sofa < sofas; sofa++) {
            while (!onSideBySide(row[sofa * 2], row[sofa * 2 + 1])) {
                int p2 = row[sofa * 2 + 1];
                int p2Partner = getPartner(p2);
                int swapIndex = getSwapPosition(map[p2Partner]);
                // Swap position
                swap(row[sofa * 2 + 1], row[swapIndex]); // swap key as index
                // update map
                swap(map[p2], map[row[swapIndex]]); // swap key as position
                ans++;
            }
        }
        return ans;
    }
};

Time complexity: O(n)

This post is based on Omkar Deshpande lecture taught on Interview Kickstart.

Happy learning.