Day -3 LC - Problem Solving
Table of contents
No headings in the article.
As Usually today, i kicked off my day with solving Lc problems, firstly i have been lagging behind a problem, so before going to this problem i have completed that one. which i will discuss at the end but this problem was the most challenging. May be in future, it might become easy as this was the first time i am solving the graph problems.
After reading the question, i figured out that the problem was based on graphs. So have developed a mental model and has 2 approaches. For this day i will post my approach towards the question. Later i will add some more details regarding the second approach.
Problem Description :
In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.
You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.
Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.
Sample Test Cases:
Example 1:
Input: n = 2, trust = [[1,2]]
Output: 2
Example 2:
Input: n = 3, trust = [[1,3],[2,3]]
Output: 3
Example 3:
Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Proposed Solution:
@code author Naveen Kumar Vadlamudi
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
values = defaultdict(list)
# O(N) For Building the Dictionary
for i in range(len(trust)):
if trust[i][1] not in values:
values[trust[i][1]] = [trust[i][0]]
else:
values[trust[i][1]].append(trust[i][0])
# Worst Case TC O(N Log N)
values = sorted(values.items(), key = lambda x : -len(x[1]))
if n == 1 and not trust:
return n
elif n > 1 and not trust:
return -1
elif len(values) == 1:
return values[0][0]
elif len(values) > 1:
judge_node = values[0][0]
judge_len = len(values[0][1])
del values[0]
res = [0 for i in range(len(values)) if judge_node in values[i][1]]
print(judge_node)
if (0 not in res) and (judge_len == n - 1 ):
return judge_node
else:
return -1
else:
return -1
## This code has been written by my own thoughts and hasnt been copied from anyone
## Needs to make many changes as i have manually added the edge cases which shouldnt be the ##case
I know that a solution of O(N Log N ) is not optimized when a code which runs at O(N) for the same input.
As of today, i have vested more than 6 hrs for this problem, approaching in different ways. which i assume will post those details detailedly when i grab some time.
1010. Pairs of Songs With Total Durations Divisible by 60
This problem, was also a beautiful one, where yesterday, i couldnt find enough time to solve it. so morning i have solved this one by seeing others approach and understood the code what it is doing.
Problem Description:
You are given a list of songs where the ith song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
Example 2:
Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Proposed Solution:
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
look_up = [0]*60
cnt = 0
for i in range(len(time)):
rem = time[i] % 60
if rem == 0:
cnt += look_up[0]
else:
cnt += look_up[60-rem]
look_up[rem] += 1
return cnt
So as of today, these are the 2 problems i have solved, and would add more details on the weekend, by explaining my approaches towards them. which i feel will provide more insight on what they are and how i approached them, in solving them. so until then stay tuned, maintain the high spirit.
Kudos Thanks for reading my Blog ! i knew that i am simply adding the solution without elaborating it , which i feel that is not so good idea, but due to the time constraints, i am doing so.