FastPrepFastPrep
Problem Brief

Skyscraper

FULLTIMEOA
See Microsoft online assessment and hiring insights

You are gien an array A of N integers, representing the maximum heights of N skyscrapers to be built.

Your task if to specify the actual heights of the skyscrapers, given that:

  • the height of the K-th skyscraper should be positive and not bigger than A[K]
  • no two skyscrapers should be of the same height
  • the toal sum of the skyscrapers' heights should be the maximum possible

    • Given an array A of N integers, returns an array B of N integers where B[K] is the assigned height of the K-th skyscraper satisfying the above conditions.

    If there are several possible answers, the function may return any of them. You may assume that it is always possible to build all skyscrapers while fulfilling all the requirements.

    1Example 1

    Input
    A = [1, 2, 3]
    Output
    [1, 2, 3]
    Explanation
    As all of the skyscrapers may be built to their maximum height.

    2Example 2

    Input
    A = [9, 4, 3, 7, 7]
    Output
    [9, 4, 3, 7, 6]
    Explanation
    Note that [9, 4, 3, 6, 7] is also a valid answer. It is not possible for the last two skyscrapers to have the same height. The height of one of them should be 7 and the other should be 6.

    3Example 3

    Input
    A = [2, 5, 4, 5, 5]
    Output
    [1, 2, 3, 4, 5]
    Explanation
    N/A

    Constraints

    Limits and guarantees your solution can rely on.

  • N is an integer within the range [1..50,000]
  • Each element of array A is an integer within the range [1..1,000,000,000]
  • There is always a solution for the given input
    • public int[] skyscraper(int[] A) {
  // write your code here
}
    Input

    A

    [1, 2, 3]

    Output

    [1, 2, 3]

    Sign in to submit your solution.