03.The Side Track

EasyArrays
Pattern lockedSolve it, or make 3 submissions, to unlock which classic problem this story hides.
Night at Bhimpur Junction. Numbered wagons go into a side track one by one and come back out in the opposite order. A board shows the order in and the order out.

// The story

Every night, goods wagons from the coal mines reach Bhimpur Junction. Station master Kavita Rao must send them to the port. Her yard has only one side track. It is closed at the far end.

The wagons are moved into the side track one by one, in the order they arrive. Later, the wagons come out from the same end. The last wagon in comes out first. The first wagon in comes out last.

When the train to the port is ready, Kavita must call the port. She must tell the port the order in which the wagons leave. Write it for her.

// Your task

You get the wagon numbers wagons in the order they arrive. All the wagons go into the side track. Then all of them come out again. Return the wagon numbers in the order they leave the side track.

  • Input: the first line is n, the number of wagons. The second line has the n wagon numbers, in the order they arrive.
  • Limits: 1 ≤ n ≤ 105 and -109 ≤ number ≤ 109.
  • Wagon numbers can be zero or negative. Two wagons can have the same number. Do not skip any wagon, even if its number repeats.
  • Output: return the wagon that leaves first at the start of your list. The program prints the list on one line, with one space between numbers.

Example 1:

Input:
6
1 4 3 2 6 5

Output:
5 6 2 3 4 1

Wagon 1 went in first. It is at the far end, so it comes out last. Wagon 5 went in last, so it comes out first.

Example 2:

Input:
4
4 5 1 2

Output:
2 1 5 4

Wagon 2 went in last, so it comes out first. Wagon 4 went in first, so it comes out last.

Example 3:

Input:
3
10 20 30

Output:
30 20 10

Wagon 30 went in last, so it comes out first. Wagon 10 went in first, so it comes out last.

// Constraints

  • 1 <= len(arr) <= 10^5
  • -10^9 <= arr[i] <= 10^9

Time limit: 1s ·  Memory limit: 256 MB

Hint 1

The first wagon goes to the far end of the side track. So it comes out last. The last wagon comes out first.

Hint 2

There are n wagons. Count places from 0. The wagon at place i in the arrival list leaves at place n - 1 - i.

Hint 3

You do not need a second list. Swap the first and last wagons. Then swap the second and second-last. Stop when you reach the middle.

Solution.java
Sample tests