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

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

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

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

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