Demilade Oyedele doyedele1

Software Engineer

doyedele1 / solution.py

Last active October 25, 2023 23:57

3. Longest Substring Without Repeating Characters

	'''
	Explanation I: Naive Solution
	- Enumerate the string and check all the substrings. Check the longest substring that have no repeating characters
	- Update the result to the count of the longest substring with no repeating characters
	abcabcbb
	- From a, we check the substring starting from a
	- From b, we check the substring starting from b

	abcabcbb
	abca --> has repeating characters. We do not need to check the next substring, which is abcab because we already have duplicates from the previous iteration.

doyedele1 / solution.py

Created October 25, 2023 23:14

56. Merge Intervals

	'''
	Explanation:
	[[1,3], [8, 10], [15, 18], [2,6]]
	1-----3
	8------10
	15--------18
	2------6
	- Sort intervals based on the start times
	[[1,3], [2,6], [8, 10], [15, 18]]
	- Add the first interval to the res nested array

doyedele1 / solution.py

Created October 25, 2023 22:56

79. Word Search

	'''
	Explanation: Recursive DFS (Backtracking) Solution
	* We can't reuse a character that we've visited before
	So, let's do the backtracking brute-force as a human would do

	word = "ABCCED"
	We check if we have an A in the board since that's the first letter in the word
	Yes, we do. Then we check all possible neighbors of A and check if we have a B

	TC: O(rc * dfs) = O(rc * 4 ^ len(word))

doyedele1 / solution.py

Created October 25, 2023 22:28

740. Delete and Earn

	'''
	TC: O(n)
	SC: O(n)
	'''

	from typing import List

	class Solution:
	def deleteAndEarn(self, nums: List[int]) -> int:
	arrNums = [0] * (max(nums) + 1)

doyedele1 / solution.py

Created October 25, 2023 22:27

797. All Paths From Source to Target

	'''
	Explanation I: DFS Recursion (Backtracking)
	Input: [[1,2],[3],[3],[]]
	Output: [[0,1,3],[0,2,3]]

	f(0, 3)
	/ \
	f(1,3) f(2,3)
	\| \|
	f(3,3) f(3,3)

doyedele1 / solution.py

Created October 25, 2023 22:22

2646. Minimize the Total Price of the Trips

	'''
	Explanation:
	- First, talk about the case where you don't half the prices of non-adjacent prices

	- Important inputs
	n = number of nodes
	edges.length = n - 1
	edgeA >= 0, edgeB <= n - 1
	tripA >= 0, tripB <= n - 1
	price.length = n

doyedele1 / solution.py

Created September 26, 2023 23:14

Insert Delete GetRandom O(1)

	'''
	Explanation:
	- We can have two data structures. An array and a hashmap
	- With the array, we can easily choose a random number from it
	- With the hashmap, we can achieve an insertion and removal of O(1)

	hashmap --> key = value, value = index
	array --> contains only the value

	Insert function

doyedele1 / solution.py

Created September 21, 2023 00:59

Decode String

	'''
	Explanation:
	- There is always guaranteed an integer right in front of an opening bracket

	54[ab6[cd]]
	stack = 5, 4, [, a, b, 6, [, c, d
	5, 4, [, a, b, 6
	We pop any integer after what we've popped which is 6 --> 6 * cd
	5, 4, [, a, b, 6*cd
	54, ab, 6*cd

doyedele1 / solution.py

Created September 7, 2023 13:48

Two City Scheduling

	class Solution:
	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
	costs = sorted(costs, key = lambda x: x[0] - x[1])

	res = 0
	n = len(costs) // 2

	for i in range(n):
	res += costs[i][0] + costs[i + n][1]

doyedele1 / design-browser-history.py

Last active March 14, 2022 09:15

Design Browser History

	'''
	Explanation:
	- history: [leetcode, youtube, facebook, google]
	- urlPosition: i
	visit: pop out all urls after the urlPosition, append the url to visit and move the urlPosition

	- history: [leetcode, youtube, facebook, google], steps = 2
	- urlPosition: i
	back and forward --> you don't want to go out of bound because of the steps