Rank Transform of Array (via Leetcode)¶

Date published: 2020-04-10

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, lists, dictionaries, zip function

This problem is on Leetcode.

Problem statement:

Given an array of integers arr, replace each element with its rank. The rank represents how large the element is in the array. 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.

Define Test Cases¶

In [16]:

# assert array_rank_transform([40, 10, 20, 30]) == [4, 1, 2, 3]

# assert array_rank_transform([40, 10, 20, 30]) == [4, 1, 2, 3]

• 40 is the 4th smallest number in the array (smaller than no other number)
• 10 is the 1st smallest number in the array (smaller than 20, 30 and 40
• 20 is the 2nd smallest number in the array (smaller than 30 and 40)
• 30 is the 3rd smallest number in the array (smaller than 40)

In [17]:

# assert array_rank_transform([100, 100, 100]) == [1, 1, 1]

# assert array_rank_transform([100, 100, 100]) == [1, 1, 1]

Remember elements of the same value can share the same rank value.

• 100 is the 1st smallest number in the array (tied with 100 and 100)
• 100 is the 1st smallest number in the array (tied with 100 and 100)
• 100 is the 1st smallest number in the array (tied with 100 and 100)

Explanation of Solution #1¶

Pseudocode for Solution #1¶

In [24]:

# create a function that takes an array as an input
    # use sorted function on input list to sort it from smallest to largest
    # assign variable rank to be integer rank value of 1
    # assign variable sorted_rank_list to store list of final ranks and just one item of 1

    # iterate over element in sorted list... 
    # iterate i from 1 to the length of the sorted_list
        # want to compare value in iteration to previous value...
        # if sorted_list[i] == sorted_list[i-1]
            # the value in sorted list is same as previous value...
            # we want rank value to stay the same for equal values...
            # don't increase rank
        # else:
            # increment rank by 1
        # append rank value to sorted_rank_list

    # assign rank_list to be an empty list

    # create rank_list values through use of sorted_list, input list and sorted_rank_list...
    # iterate over each item in original input list
        # for every index, element in enumerate(sorted_list):
            # if element is equal to item
                # want to find equivalent ranking for that number in sorted_list
                # append sorted_rank_list[index] to rank_list
                # break out of for loop to move to next number in original array
    # return rank_list

# create a function that takes an array as an input # use sorted function on input list to sort it from smallest to largest # assign variable rank to be integer rank value of 1 # assign variable sorted_rank_list to store list of final ranks and just one item of 1 # iterate over element in sorted list... # iterate i from 1 to the length of the sorted_list # want to compare value in iteration to previous value... # if sorted_list[i] == sorted_list[i-1] # the value in sorted list is same as previous value... # we want rank value to stay the same for equal values... # don't increase rank # else: # increment rank by 1 # append rank value to sorted_rank_list # assign rank_list to be an empty list # create rank_list values through use of sorted_list, input list and sorted_rank_list... # iterate over each item in original input list # for every index, element in enumerate(sorted_list): # if element is equal to item # want to find equivalent ranking for that number in sorted_list # append sorted_rank_list[index] to rank_list # break out of for loop to move to next number in original array # return rank_list

Code for Solution #1¶

In [19]:

def array_rank_transform(arr):       
    sorted_list = sorted(arr)
    rank = 1
    # seed initial rank as 1 because that's first item in input list
    sorted_rank_list = [1]
    for i in range(1, len(sorted_list)):
        if sorted_list[i] != sorted_list[i-1]:
            rank += 1
        sorted_rank_list.append(rank)
    rank_list = []
    for item in arr:
        for index, element in enumerate(sorted_list):
            if element == item:
                rank_list.append(sorted_rank_list[index])
                # we want to break out of inner for loop
                break
    return rank_list

def array_rank_transform(arr): sorted_list = sorted(arr) rank = 1 # seed initial rank as 1 because that's first item in input list sorted_rank_list = [1] for i in range(1, len(sorted_list)): if sorted_list[i] != sorted_list[i-1]: rank += 1 sorted_rank_list.append(rank) rank_list = [] for item in arr: for index, element in enumerate(sorted_list): if element == item: rank_list.append(sorted_rank_list[index]) # we want to break out of inner for loop break return rank_list

Verify Solution #1 with Test Cases¶

In [20]:

assert array_rank_transform([40, 10, 20, 30]) == [4, 1, 2, 3]

assert array_rank_transform([40, 10, 20, 30]) == [4, 1, 2, 3]

In [21]:

assert array_rank_transform([100, 100, 100]) == [1, 1, 1]

assert array_rank_transform([100, 100, 100]) == [1, 1, 1]

In [22]:

assert array_rank_transform([1, 3, 3, 5]) == [1, 2, 2, 3]

assert array_rank_transform([1, 3, 3, 5]) == [1, 2, 2, 3]

Complexity of Solution #1¶

Let n be the count of values in the input list.

Space complexity:

• sorted_list will hold n values and therefore is O(n)
• sorted_rank_list will hold n values and is O(n)
• rank_list will hold n values and is O(n)

Total space complexity is O(3n). The 3 is insignificant so I'll round to O(n).

Time complexity:

• Sort the input list is an O(nlogn) operation
• Iteration over every value in sorted_list is O(n)
• Iteration over each value in arr - the input list - is O(n)
• Iteration over each index and value in sorted_list up to finding an equivalent value in the input list should be on average O(n/2); the division by 2 is insignificant so this will be O(n).

Total time eomplexity is also O(nlogn) + O(n) + O(n) + O(n) which equals O(3nlogn). The 3 is insignificant so I'll round to O(nlogn).

Explanation of Solution #2¶

Pseudocode for Solution #2¶

In [ ]:

# create a function that takes an array as an input
    # use sorted function on input list to sort it from smallest to largest
    # assign variable rank to be integer rank value of 1
    # assign variable sorted_rank_list to store list of final ranks and just one item of 1

    # iterate over element in sorted list... 
    # iterate i from 1 to the length of the sorted_list
        # want to compare value in iteration to previous value...
        # if sorted_list[i] is not equal to sorted_list[i-1]
            # increment rank by 1
        # append rank value to sorted_rank_list

    # rank_list and sorted_list are the same size...
    # create dictionary with each item as a key and its rank as the value...
    # dictionary called item_rank_dict
    # assign rank_list to be an empty list
    
    # iterate over each item in original input list
        # lookup rank of item in item_rank_dict and append value to rank_list
    # return rank_list

# create a function that takes an array as an input # use sorted function on input list to sort it from smallest to largest # assign variable rank to be integer rank value of 1 # assign variable sorted_rank_list to store list of final ranks and just one item of 1 # iterate over element in sorted list... # iterate i from 1 to the length of the sorted_list # want to compare value in iteration to previous value... # if sorted_list[i] is not equal to sorted_list[i-1] # increment rank by 1 # append rank value to sorted_rank_list # rank_list and sorted_list are the same size... # create dictionary with each item as a key and its rank as the value... # dictionary called item_rank_dict # assign rank_list to be an empty list # iterate over each item in original input list # lookup rank of item in item_rank_dict and append value to rank_list # return rank_list

Code for Solution #2¶

In [ ]:

def array_rank_transform(arr):       
    sorted_list = sorted(arr)
    rank = 1
    sorted_rank_list = [1]
    for i in range(1, len(sorted_list)):
        if sorted_list[i] != sorted_list[i-1]:
            rank += 1
        sorted_rank_list.append(rank)
    
    rank_list = [] 
    # zip function returns iterator of tuple pairs of matching values in two inputss
    # dict function casts 1nd value in tuple as key and 2nd value in tuple as value
    item_rank_dict = dict(zip(sorted_list, sorted_rank_list))
    
    for item in arr:
        item_rank = item_rank_dict[item]
        rank_list.append(item_rank)
    return rank_list

def array_rank_transform(arr): sorted_list = sorted(arr) rank = 1 sorted_rank_list = [1] for i in range(1, len(sorted_list)): if sorted_list[i] != sorted_list[i-1]: rank += 1 sorted_rank_list.append(rank) rank_list = [] # zip function returns iterator of tuple pairs of matching values in two inputss # dict function casts 1nd value in tuple as key and 2nd value in tuple as value item_rank_dict = dict(zip(sorted_list, sorted_rank_list)) for item in arr: item_rank = item_rank_dict[item] rank_list.append(item_rank) return rank_list

Complexity for Solution #2¶

Let n be the count of values in the input list.

Space complexity:

• sorted_list will hold n values and therefore is O(n)
• sorted_rank_list will hold n values and is O(n)
• rank_list will hold n values and is O(n)
• item_rank_dict will hold n values and is O(n)

Total space complexity is O(4n). The 4 is insignificant so I'll round to O(n).

Time complexity:

• Sort the input list is an O(nlogn) operation
• Iteration over every value in sorted_list is O(n)
• Creation of item_rank_dict is an O(n) operation
• Iteration over each value in arr - the input list - is O(n)

Total time complexity is O(3nlogn). The 3 is insignificant so I'll round to O(nlogn).

Verify Test Cases for Solution #2¶

In [27]:

assert array_rank_transform([40, 10, 20, 30]) == [4, 1, 2, 3]

assert array_rank_transform([40, 10, 20, 30]) == [4, 1, 2, 3]

In [28]:

assert array_rank_transform([100, 100, 100]) == [1, 1, 1]

assert array_rank_transform([100, 100, 100]) == [1, 1, 1]

In [29]:

assert array_rank_transform([1, 3, 3, 5]) == [1, 2, 2, 3]

assert array_rank_transform([1, 3, 3, 5]) == [1, 2, 2, 3]