The question is from code fight which states: An infinite number of boxes are arranged in a row and numbered from left to right. The first box on the left is number 1, the next box is number 2, etc. n balls are placed in n of the boxes, and there can only be one ball per box. You want to organize the balls, so you decide to arrange all the balls next to each other. They should occupy a contiguous set of boxes. You can take one ball and move it into an empty box in one move.
Given an array balls that indicates the numbers of the boxes in which the balls are placed, find the minimum number of moves needed to organize the balls.
Example
For balls = [6, 4, 1, 7, 10], the output should be ballsRearranging(balls) = 2.
In this example, the minimum number of moves needed to arrange the balls next to each other is 2. You could move the ball in box 1 to box 5 and the ball in box 10 to box 8 (or to box 3).
Currently my code is:
def ballsRearranging(balls):
ballsLength = len(balls)
partial = ballsLength//2 #INITIALLY SET TO HALF
setBalls = set(balls)
sortedBalls = sorted(balls)
minimum = 1000000
#####CHECK IF ITS ALREADY ORGANIZED
#####FIRST NUM PLUS LENGTH - 1 IS EQUAL TO THE LAST NUM
if sortedBalls[0]+ballsLength-1 == sortedBalls[-1]:
return 0
for i,num in enumerate(sortedBalls):
#####NO NEED TO GO PASS HALF WAY SINCE THAT AUTOMATICALLY MEANS HALF WILL BE OUT OF RANGE
#####THIS VALUE DYNAMICALLY CHANGES TO THE SMALLEST FRACTION OF OUT OF RANGE FOUND
if i >= partial:
break
#####IF WE TAKE THIS NUM AS THE BEGINNING, ORDERED BALLS WILL GO UP TO THE RANGE RNG
rng = range(num,num+ballsLength)
#####BALLS ALREADY IN THE RANGE RNG, WE WONT BE MOVING THESE BALLS
inRange = setBalls & set(rng)
#####BALLS NOT IN RANGE, EACH WILL BE REQUIRED TO MOVE
#####THE LENGTH OF THIS WILL BE THE NUMBER OF MOVES REQUIRED
outRange = setBalls - set(rng)
lenOutRange = len(outRange)
if lenOutRange < minimum:
minimum = lenOutRange
partial = 100*(lenOutRange/ballsLength) #UPDATE THE PARTIAL VALUE
This works fine but currently times out with the time limit of 4s on the hidden tests. Basically my algorithm goes from the smallest number to a specific partial (fraction) of the given array. It checks where the original set intersects with the given range. Whichever has the least amount of out of range items, will be the minimum number of changes/rearranging to be made. Was wondering whats the better algorithm, preferably in python.
This code is careful to compute the result in O(n log n) time. Or if the balls are already sorted, this runs in O(n) time.
It uses a caterpillar algorithm: for each j, indexed into the sorted array of balls, i is incremented until it contains the first ball within n-1 of the ball at index j. That makes it easy to count the number of balls in the range that ends with the j'th ball.
def balls_rearranging(balls):
balls.sort()
best = 0
i = 0
for j in xrange(len(balls)):
while balls[i] <= balls[j] - len(balls):
i += 1
best = max(best, j - i + 1)
return len(balls) - best
print balls_rearranging(range(0, 10000000, 2))