Day 1: My Leetcode Adventure[2]

How many problems have I solved? Uno
Leetcode 1920: Build Array from Permutation

*Return same-length zero-based permutation nums array[array of distinct integers from 0 to nums.length-1] in which ans[i] = nums[nums[i]] where 0<=i< nums.length. *

My Answer
This is the first problem I had for the Weekly Contest 248. On top of that, it has been a while since I visited this website. I am starting the grind to secure a job after graduation.

newArr=[]
        for i in range(len(nums)):
            # Calculate the new val
            temp=nums[nums[i]]
            newArr.append(temp)
        return newArr

Better Solution

return [nums[nums[i]] for i in range(len(nums))]

Even BetterSolution

return [nums[i] for i in nums]

What I learned?

1. List comprehensions can reduce code snippets
2. Sometimes I am extra like finding the same element[Ex. nums[i]] Instead of... newArr=[] for i in range(len(nums)): # Calculate the new val temp=nums[nums[i]] newArr.append(temp) return newArr Do...

return [nums[i] for i in nums]

Leetcode 1921: Build Array from Permutation

*Given monsters arr and speed arr where monster i travels at speed j. You are allowed to kill any monsters starting from minute 0. Keep in mind that monsters are not allowed to be killed in the middle of a minute and only one monster can be killed at the start of the minute. If monster reaches city == start of the minute, you still lose. Return the max numbers of monsters you can kill before the monster reach your city. *

Answer
I had trouble with this question because I was not able to solve it completely with 3 attempts. Every attempt got me closer to the answer.

1. Attempt 1 = 53/150 Cases passed
2. Attempt 2 = 105/150 Cases
3. Attempt 3 = 116/130 Cases

Attempt 1

killed=0
        while dist or sum(1 for d in dist if d<0)>0:
            killed +=1 
            #Remove 1st monster
            dist.pop(0)
            speed.pop(0)
            # Subtract dist and speed 
            for i in range(len(dist)):
                dist[i]-=speed[i]
        return killed

My first approach was to kill the first monster, but it is flawed because the other monsters could be faster. In addition, the second condition[sum(1 for d in dist if d<0)>0] doesn't make sense. It should stop iterating if monster reached the city.
Attempt 2

killed=0
        # print(sum(1 for d in dist if d<=0))
        while dist and sum(1 for d in dist if d<=0)==0:
            print(dist)
            print(speed)
            # print("Killing...")
            for i in range(len(dist)):
                dist[i]-=speed[i]
            print(dist)
            # Remove a monster 
            delMon=[ind for ind,elem in enumerate(dist) if elem <=0]
            delMonInd= delMon[0] if delMon else dist.index(min(dist))
            print("Killed #", killed,", Index:",delMonInd, ", Value:",dist[delMonInd] )
            dist.pop(delMonInd)
            speed.pop(delMonInd)

            killed +=1 
        return killed

2nd approach was to dist-speed and then find all monster that have entered the city and remove 1st occurence. The problem is for the else condition where some monster can advance to the city faster so I can't just remove the monster with the shortest distance.
Attempt 3

killed=0
        while dist and sum(1 for d in dist if d<=0)==0:
            for i in range(len(dist)):
                dist[i]-=speed[i]
            # Remove a monster 
            delMon=[ind for ind,elem in enumerate(dist) if elem <=0]
            special=[]
            for i in range(len(dist)):
                special.append(int(dist[i]/speed[i]))
            # delMonInd= delMon[0] if delMon else self.turnsLeft(dist,speed)
            delMonInd= delMon[0] if delMon else special.index(min(special))
            dist.pop(delMonInd)
            speed.pop(delMonInd)
            killed +=1 

            # print("Killed #", killed,", Index:",delMonInd )
        return killed

3rd approach was to take current result and perform division between distance and speed. This helps resolve the closest monster problem and this is the right approach. However, time exceeded for this approach.
Better Solution

arr=[]
            #Store the minute time for each monster
            for i in range(len(dist)):
                minute=math.ceil(dist[i]/speed[i] )
                arr.append(minute)
            arr.sort()
            killed=0
            #Count number of monster killed
            for m in range(len(arr)):
                if(arr[m]<=m):
                    return killed
             killed+=1
            return killed

This sorting approach is O(nlogn) which is simple and fast. First, it converts to comparable units. Then it sorts to decide which monster to remove during minute m. Remove monsters until monster has reached the city. *
**What I learned?*

1. How to check array for emptiness? if arr: T else F
2. How to write a ternary operator in Python? "Y" if T else 'N'
3. How to move elements from array? .pop()!!!
4. Condition should be better
5. math.ceil() vs math.floor()
6. Reassigning func list has no effect on outside
7. Include code to main flow--> Transfer to a function
8. zip(lst1,lst2)--> Create a zip object of tuple pairs from both list