Crack the Amazon Coding Interview

I will cover a recent question asked in Amazon Interview Round for the Position of Software Development Engineer in the US.

Plan :
1. Explain the problem
2. Discussion of algorithm
3. Final Code in Java

Although I will provide the code in Java, the algorithm will also be written as pseudocode so that it can be easily converted to any language.
Time Complexity, Space Complexity, Optimal Solutions, and alternate approaches will also be discussed.