Leetcode Problem 2459. Sort Array by Moving Items to Empty Space

2459. Sort Array by Moving Items to Empty Space

Leetcode Solutions

Value to Index Array Transformation for a fast, O(n), sorting strategy.

  1. Convert the original array into a number-to-index array (numsPos), where the index represents the value in the original array and the value at that index is the position of that number in the original array.
  2. Define a function inPosition that takes numsPos and a start parameter to determine the sorting strategy (0 for empty space at the end, 1 for empty space at the beginning).
  3. In inPosition, iterate through numsPos and swap the zero with the first number that is not in the correct position.
  4. If zero is already in the correct terminal position, find the first number not in the correct position and swap it with zero.
  5. Count the number of swaps and return it.
  6. Run inPosition twice with different start values and return the minimum of the two results.
UML Thumbnail

O(N) time. Graph intuition.

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...