Grokking the Coding Interview: Patterns for Coding Questions
Vote

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!
J

Jack Tan

· 10 months ago

The constraint should be 1 <= nums[i] <= n.

J

Jack Tan

· 10 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
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];
}
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
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;
  }
};
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
Harsh Chiki

Harsh Chiki

· 2 years ago

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

Show 1 reply
quil

quil

· 3 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.

balamurali.manickavasagam

balamurali.manickavasagam

· 3 years ago

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

if (i !=j)
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

Reading Progress

0%