Jobs

Interviews

Discussions

Rank Transform of an Array

Easy

Microsoft

0 views

Topics:

Arrays

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints:

0 <= arr.length <= 10⁵
-10⁹ <= arr[i] <= 10⁹

Rank Transform of an Array

Easy

Microsoft

0 views

Topics:

Arrays

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints:

0 <= arr.length <= 10⁵
-10⁹ <= arr[i] <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array?
Is the input array guaranteed to be non-empty?
How should I handle duplicate values in the array when assigning ranks? Should they share the same rank?
Is the order of the output array required to match the order of the input array?
Are there any specific constraints on the memory usage of my solution?

Brute Force Solution

Approach

The problem asks us to assign a rank to each number in a list, where the smallest number gets rank 1, the next smallest gets rank 2, and so on. The brute force way is to check every possible rank assignment and see if it satisfies the rules.

Here's how the algorithm would work step-by-step:

First, make a list of all the numbers in the input.
Next, for each number, try giving it every possible rank, starting from 1.
After assigning a rank to a number, check if that assignment makes sense based on the ranks that have already been assigned to other numbers.
Specifically, if a smaller number has a higher rank or a larger number has a lower rank, then that assignment is invalid and you should try a different rank for that number.
Keep trying rank assignments until you find a valid assignment for all the numbers.
If multiple valid rank assignments are possible, then find one that follows some defined rules and return the list of ranks.

Code Implementation

def rank_transform_brute_force(array):
    original_array = list(array)
    array_length = len(array)
    ranks = [0] * array_length

    def is_valid_rank_assignment(current_ranks):
        for i in range(array_length):
            for j in range(array_length):
                if array[i] < array[j] and current_ranks[i] > current_ranks[j]:
                    return False
                if array[i] > array[j] and current_ranks[i] < current_ranks[j]:
                    return False
        return True

    def find_rank_assignment(index):
        if index == array_length:
            if is_valid_rank_assignment(ranks):
                return True
            else:
                return False

        for rank in range(1, array_length + 1):
            ranks[index] = rank
            if find_rank_assignment(index + 1):
                return True

        return False

    find_rank_assignment(0)

    # Map original values to assigned ranks
    value_to_rank = {}
    for i in range(array_length):
        value_to_rank[original_array[i]] = ranks[i]

    sorted_values = sorted(list(set(original_array)))
    rank_map = {value: i + 1 for i, value in enumerate(sorted_values)}

    #Assign a rank based on the relative order of the values
    result = [rank_map[value] for value in original_array]

    return result

Big(O) Analysis

Time Complexity

O(n^3) – The described algorithm iterates through each of the n numbers in the input array. For each number, it tries assigning ranks from 1 to n. After each rank assignment, it checks the validity of this assignment against all other already assigned ranks, which takes O(n) time per assignment. Since, in the worst-case, assigning a rank will require checking against all possible assignments, the time complexity will be O(n) * O(n) * O(n) which simplifies to O(n^3).

Space Complexity

O(N) – The brute force approach, as described, initially creates a list of all numbers from the input array, which takes O(N) space where N is the number of elements in the input array. Additionally, it implicitly stores the 'ranks that have already been assigned to other numbers' to perform validation. In the worst case, this will require storing N ranks. Therefore, the overall space complexity is dominated by the list of numbers and the stored ranks, resulting in O(N) auxiliary space.

Optimal Solution

Approach

To assign ranks to elements in an array, we want to give smaller elements smaller ranks and larger elements larger ranks. The efficient approach involves sorting to understand the relative order and then mapping each element to its appropriate rank in a sequential order.

Here's how the algorithm would work step-by-step:

First, create a sorted list of all the unique numbers present in the original list.
Next, assign a rank to each unique number in the sorted list, starting with rank 1 for the smallest number, rank 2 for the next smallest, and so on.
Finally, go through the original list, and for each number, find its corresponding rank from the assigned rank mapping.

Code Implementation

def rank_transform(array):
    sorted_unique_numbers = sorted(list(set(array)))

    # Assign ranks based on sorted order.
    rank_map = {}
    current_rank = 1

    for number in sorted_unique_numbers:
        rank_map[number] = current_rank
        current_rank += 1

    # Map elements in original array to their ranks
    ranked_array = []
    for number in array:

        ranked_array.append(rank_map[number])

    return ranked_array

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the unique elements of the input array, which takes O(n log n) time, where n is the length of the input array. Creating a sorted list of unique numbers requires iterating through the original list once (O(n)), and the mapping from numbers to ranks takes another iteration (O(n)). Finding the corresponding rank for each element involves iterating through the original array (O(n)) and performing a lookup in the rank mapping, which can be done in O(1) time using a hashmap (or potentially O(log n) if a tree-based map is used). Since sorting takes O(n log n) time and the remaining operations are linear O(n), the overall time complexity is O(n log n).

Space Complexity

O(N) – The algorithm uses a sorted list of unique numbers from the original list, which in the worst case (where all elements are unique) will be of size N, where N is the number of elements in the input array. It also uses a rank mapping (dictionary or hash map) to store the rank of each unique number, which can also grow up to size N in the worst case. Therefore, the auxiliary space is proportional to N. Consequently, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty array if the input is null or empty.
Array with one element	Return an array containing only the rank 1.
Array with all identical values	All elements should be ranked 1.
Array with duplicate values scattered throughout	The same rank should be assigned to duplicate elements.
Array with negative numbers	The ranking should still be based on the sorted order regardless of the sign.
Array with a mix of positive, negative and zero values	The ranking should correctly reflect the order of all elements, including zero.
Array with large input size nearing memory limits	Ensure the solution's memory usage remains within reasonable bounds (e.g., avoids unnecessary copies).
Array with numbers close to integer limits (Integer.MAX_VALUE and Integer.MIN_VALUE)	Handle edge cases to prevent any possible Integer overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array?
Is the input array guaranteed to be non-empty?
How should I handle duplicate values in the array when assigning ranks? Should they share the same rank?
Is the order of the output array required to match the order of the input array?
Are there any specific constraints on the memory usage of my solution?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, make a list of all the numbers in the input.
Next, for each number, try giving it every possible rank, starting from 1.
After assigning a rank to a number, check if that assignment makes sense based on the ranks that have already been assigned to other numbers.
Specifically, if a smaller number has a higher rank or a larger number has a lower rank, then that assignment is invalid and you should try a different rank for that number.
Keep trying rank assignments until you find a valid assignment for all the numbers.
If multiple valid rank assignments are possible, then find one that follows some defined rules and return the list of ranks.

Code Implementation

def rank_transform_brute_force(array):
    original_array = list(array)
    array_length = len(array)
    ranks = [0] * array_length

    def is_valid_rank_assignment(current_ranks):
        for i in range(array_length):
            for j in range(array_length):
                if array[i] < array[j] and current_ranks[i] > current_ranks[j]:
                    return False
                if array[i] > array[j] and current_ranks[i] < current_ranks[j]:
                    return False
        return True

    def find_rank_assignment(index):
        if index == array_length:
            if is_valid_rank_assignment(ranks):
                return True
            else:
                return False

        for rank in range(1, array_length + 1):
            ranks[index] = rank
            if find_rank_assignment(index + 1):
                return True

        return False

    find_rank_assignment(0)

    # Map original values to assigned ranks
    value_to_rank = {}
    for i in range(array_length):
        value_to_rank[original_array[i]] = ranks[i]

    sorted_values = sorted(list(set(original_array)))
    rank_map = {value: i + 1 for i, value in enumerate(sorted_values)}

    #Assign a rank based on the relative order of the values
    result = [rank_map[value] for value in original_array]

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a sorted list of all the unique numbers present in the original list.
Next, assign a rank to each unique number in the sorted list, starting with rank 1 for the smallest number, rank 2 for the next smallest, and so on.
Finally, go through the original list, and for each number, find its corresponding rank from the assigned rank mapping.

Code Implementation

def rank_transform(array):
    sorted_unique_numbers = sorted(list(set(array)))

    # Assign ranks based on sorted order.
    rank_map = {}
    current_rank = 1

    for number in sorted_unique_numbers:
        rank_map[number] = current_rank
        current_rank += 1

    # Map elements in original array to their ranks
    ranked_array = []
    for number in array:

        ranked_array.append(rank_map[number])

    return ranked_array

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty array if the input is null or empty.
Array with one element	Return an array containing only the rank 1.
Array with all identical values	All elements should be ranked 1.
Array with duplicate values scattered throughout	The same rank should be assigned to duplicate elements.
Array with negative numbers	The ranking should still be based on the sorted order regardless of the sign.
Array with a mix of positive, negative and zero values	The ranking should correctly reflect the order of all elements, including zero.
Array with large input size nearing memory limits	Ensure the solution's memory usage remains within reasonable bounds (e.g., avoids unnecessary copies).
Array with numbers close to integer limits (Integer.MAX_VALUE and Integer.MIN_VALUE)	Handle edge cases to prevent any possible Integer overflow.