Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Cyclic Sort

Problem Statement

We are given an array containing n objects. Each object, when created, was assigned a unique number from the range 1 to n based on their creation sequence. This means that the object with sequence number 3 was created just before the object with sequence number 4.

Write a function to sort the objects in-place on their creation sequence number in O(n) and without using any extra space. For simplicity, let’s assume we are passed an integer array containing only the sequence numbers, though each number is actually an object.

Example 1:

.....

.....

.....

Like the course? Get enrolled and start learning!
balamurali.manickavasagam

balamurali.manickavasagam

· 2 years ago

It still works with the below condition instead of if ( nums[i] != nums[j])

if (i !=j)
Vladimir Surcov

Vladimir Surcov

· a year ago

This is swap without extra space

public void swap(int arr[], int i, int j) {
    arr[j] = arr[i] + arr[j];
    arr[i] = arr[j] - arr[i];
    arr[j] = arr[j] - arr[i];
}
E

eric

· 5 years ago

The time complexity part has a typo for its' first sentence. The end part should say "...above algorithm is O(N)"

Show 1 reply
A

Adil

· 3 years ago

This approach leads to a infinite loop:

class Solution:
  def sort(self, nums):
    i = 0

    while i < len(nums):
      if nums[i] != nums[nums[i] - 1]:
        nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
      else:
        i+=1
    return nums

But if I use a separate variable j = nums[I] - 1

it runs fine

What is the issue?

Show 1 reply
quil

quil

· 2 years ago

I had the same code as the solution except that in the Swap function I used the same int array name "nums" and it had weird behavior where the last entry is incorrect. When I changed it to a different name, like "arr" in the solution, it worked fine. I'm not sure if there is some hidden global variable names "nums" that is causing this weird behavior?

I thought I was going crazy because I couldn't find any difference in the logic of the code.

Harsh Chiki

Harsh Chiki

· 2 years ago

Shouldn't "nums[i] != nums[j]" be "i != nums[j]"?

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def sort(self, nums):
    
    def swap(i, j):
      temp = nums[i]
      nums[i] = nums[j]
      nums[j] = temp
    
    for i in range(len(nums)):
      # while the nums[i] is not in position keep swapping it
      while nums[i] != i + 1:
        swap(i, nums[i] - 1)

    return nums
L

lejafilip

· 2 years ago

Ofc it is just personally and we use std::swap.

class Solution {
public:
  vector<int> sort(vector<int> &nums) {
    auto i = 0;
    
    while(i < nums.size())
    {
      if(nums[i] == i + 1)
      {
          i++;
          continue;
      }
      auto jumpValue = nums[i];
      std::swap(nums[i], nums[jumpValue - 1]);
    }

    return nums;
  }
};
Venkatesh Vinayakarao

Venkatesh Vinayakarao

· 2 years ago

I am struggling to find an example where that would not be the case. In fact, a solution that simply returns the nums array set to 1 .. n is accepted as correct. Are duplicate numbers allowed?

Show 1 reply
J

Jack Tan

· 9 months ago

Why can't we just do this?

public class Solution {

  public int[] sort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
      nums[i] = i + 1;
    }
    return nums;
  }
}
Show 1 reply