Python Beginner Algorithms Tutorial

Rank Transform of Array (via Leetcode)

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]
  • 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]

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 

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

Verify Solution #1 with Test Cases

In [20]:
assert array_rank_transform([40, 10, 20, 30]) == [4, 1, 2, 3]
In [21]:
assert array_rank_transform([100, 100, 100]) == [1, 1, 1]
In [22]:
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 

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

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]
In [28]:
assert array_rank_transform([100, 100, 100]) == [1, 1, 1]
In [29]:
assert array_rank_transform([1, 3, 3, 5]) == [1, 2, 2, 3]