Justin Chan

Posted on

# 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. *

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. *

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