Hex.*

Algo-MinRewards

Posted on In
A hard question solved in 15 minutes. Use 'peaks and valley' technique to solve this question. But there are still something to improve.

Questions

Imagine that you are a teacher who is just graded the final exam in a class. You have a list of student scores on the final exam in a particular order (not necessarily sorted), and you want to reward your students. You decide to do so fairly by giving them arbitrary rewards following two rules:

  1. All students must receive at least one reward
  2. Any given student must receive strictly more rewards than an adjacent student (a student immediately to the left or to the right) with a lower score and must receive strictly fewer rewards than an adjacent student with a higher score.
    Write a function that takes in a list of scores and returns the minimum number of rewards that you must give out to students to satisfy the two rules.
    You can assume that all students have different scores; in other words, the scores are all unique.
1
2
3
4
#input
scores = [8,4,2,1,3,6,7,9,5]
#output
25 # you would give out the following rewards: [4, 3, 2, 1, 2, 3, 4, 5, 1]

Ideas

I am very happy to pass this question once in 15 minutes. The main personal ideas are as follows:

  • For the first traverse, first find out the local minimum and local maximum. The local minimum is directly set to 1, and the local maximum is set to’x’ because I don’t know what it is.
  • For the second traverse, expand left to right in the direction of 1, during the process of expanding to the left, if it exceeds the boundary and encounters’x’ and stops, during the process of expanding to the right, if it exceeds the boundary and encounters’x’ stop
  • For the third traverse, it stops where it encounters ‘x’, compare the numbers on the left and right, the larger number + 1 is the value of x
  • Return sum (rewards)

Several key points

  • orders matter
  • the scores are unique
  • all numbers are positive

Several methods given in AlgoExpert:

1. naive algorithm

  • Starting from the first number, the first number is set to 1, from left to right, if it is smaller than the previous number, it is currently changed to 1, and 1 is added to the front
  • Disadvantages: need back tracking/iterate back to the previous one.
    Time: O(n^2), Space: O(n)

2. techniques: peaks and valleys/high points and low points/ local maxes and local mins

  • I use this method
  • if I am at a local min, start expanding to the left and expanding to the right, until I reach the peaks and incrementing
  • stop once I get a peak or boundary
  • But unlike my method, I found peaks and valleys, but the video only needs valleys, not peaks
  • Time: O(n), Space: O(n)
  • Disadvantages: The code is relatively long, so many edge cases need to be considered

3. The best way, cleverest solution

  • the idea of ​​expanding to left and to right of local mins doesn’t actually have to happen by starting at the local mins
  • Just go from left to right, then from right to left, traverse twice, and set all numbers at the beginning to be 1.
  • From left to right: start from the second number, compare with the left, if the current number is smaller than the left, skip it, if it is larger, start adding 1
  • From right to left: If the current number is smaller than the right, the right starts to add
  • Advantages: There is no need to consider many edge cases, and the code is clearer, but no faster than method two
  • Time: O(n), Space: O(n)

My Solution

Peaks and Valleys

First solution

  • peaks and valleys (original solution without refering to any materials)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    def minRewards(scores):
        # Write your code here.
    	rewards = [0] * len(scores)
    	cur = 0
    	if len(scores) == 1:
    		return 1
    	if scores[0] < scores[1]:
    		rewards[0] = 1
    	if scores[-1] < scores[-2]:
    		rewards[-1] = 1
        for i in range(1, len(scores)-1):
    		if scores[i] < scores[i-1] and scores[i] < scores[i+1]:
    			rewards[i] = 1
    		elif scores[i] > scores[i-1] and scores[i] > scores[i+1]:
    			rewards[i] = "x"
    		
    	for j in range(len(rewards)):
    		if rewards[j] == 1:
    			left = j-1
    			while left >= 0 and rewards[left] != 'x':
    				rewards[left] += rewards[left+1]+1
    				left-=1
    			right = j+1
    			while right < len(rewards) and rewards[right] !='x':
    				rewards[right] = rewards[right-1]+1
    				right+=1
    				
    	for k in range(len(rewards)):
    		if rewards[k] == 'x':
    			rewards[k] = max(rewards[k-1], rewards[k+1])+1	
    	return sum(rewards)

Best Solution

Clean and better solution

  • Need to pay attation to researsed traverse.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #看了视频以后写的代码，比较绕的是reversed traverse
    def minRewards(scores):
        # Write your code here.
        rewards = [1] * len(scores)
    	for i in range(1, len(scores)):
    		if scores[i-1] < scores[i]:
    			rewards[i] +=rewards[i-1]
    	for j in reversed(range(1, len(scores))):
    		if scores[j-1] > scores[j]:
    			rewards[j-1] = max(rewards[j-1], 1+rewards[j])
    	return sum(rewards)

Tips

my way:

  • rewards = [1]*len(scores)
    better way:
  • rewards = [1 for _ in scores]