Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Cyclic Sort (easy)

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) 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!
A

Anonymous

· 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;
  }
};
A

Anonymous

· 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
A

Anonymous

· 2 years ago

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

Show 1 reply
A

Anonymous

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

A

Anonymous

· 3 years ago

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

if (i !=j)
A

Anonymous

· 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
A

Anonymous

· 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

Reading Progress

0%

Vote for new content