Skip to content

Commit ae347d4

Browse files
rubix-coderrubix-coder
committed
Day 1
1 parent 32798b7 commit ae347d4

27 files changed

+1729
-0
lines changed

‎leetcode-master/arrays_and_hashing/contains_duplicate.py

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
"""
2+
Url : https://leetcode.com/problems/contains-duplicate/description/
3+
4+
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
5+
6+
7+
8+
Example 1:
9+
10+
Input: nums = [1,2,3,1]
11+
Output: true
12+
Example 2:
13+
14+
Input: nums = [1,2,3,4]
15+
Output: false
16+
Example 3:
17+
18+
Input: nums = [1,1,1,3,3,4,3,2,4,2]
19+
Output: true
20+
21+
22+
Constraints:
23+
24+
1 <= nums.length <= 105
25+
-109 <= nums[i] <= 109
26+
"""
27+
28+
from typing import List
29+
30+
31+
# Solution 1
32+
# Cons: Time limit exceeded
33+
class Solution1:
34+
def containsDuplicate(self, nums: List[int]) -> bool:
35+
arrays = []
36+
37+
for i in nums:
38+
if i not in arrays:
39+
arrays.append(i)
40+
else:
41+
return True
42+
return False
43+
44+
45+
# Solution 2
46+
class Solution2:
47+
def containsDuplicate(self, nums: List[int]) -> bool:
48+
arrays = set(nums)
49+
50+
if len(arrays) == len(nums):
51+
return False
52+
return True
53+
54+
55+
"""
56+
Runtime
57+
425 ms Beats 31.28% of users with Python3
58+
Memory
59+
31.98MB Beats 59.59% of users with Python3
60+
"""
61+
62+
63+
# Solution 3
64+
class Solution3:
65+
def containsDuplicate(self, nums: List[int]) -> bool:
66+
nums.sort()
67+
68+
for i in range(len(nums) - 1):
69+
if nums[i] == nums[i + 1]:
70+
return True
71+
return False
72+
73+
74+
"""
75+
Runtime
76+
466 ms Beats 5.07% of users with Python3
77+
Memory
78+
28.32 MB Beats 93.65 of users with Python3
79+
"""
80+
81+
# Solution 4 (JP)
82+
class Solution4:
83+
def containsDuplicate(self, nums: List[int]) -> bool:
84+
return len(set(nums))!= len(nums)
85+
86+
"""
87+
419 ms Beats 51.40%
88+
31.95 MB Beats 44.45%
89+
"""

‎leetcode-master/arrays_and_hashing/encode_decode_strings.py

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
"""
2+
Problem: Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Please implement encode and decode
3+
4+
Example(s):
5+
6+
Example1
7+
8+
Input: [“lint”,“code”,“love”,“you”] Output: [“lint”,“code”,“love”,“you”] Explanation: One possible encode method is: “lint:;code:;love:;you”
9+
10+
Example2
11+
12+
Input: [“we”, “say”, “:”, “yes”] Output: [“we”, “say”, “:”, “yes”] Explanation: One possible encode method is: “we:;say:;:::;yes”
13+
"""
14+
15+
16+
class Solution:
17+
18+
def encode(self, strs):
19+
encode_str = ""
20+
for s in strs:
21+
encode_str += f"{len(s)}#{s}"
22+
return encode_str
23+
24+
def decode(self, str):
25+
result = []
26+
i = 0
27+
while i < len(str):
28+
j = i
29+
while str[j] != "#":
30+
j += 1
31+
length = int(str[i:j])
32+
result.append(str[j + 1: j + 1 + length])
33+
i = j + 1 + length
34+
return result
35+
36+
37+
s = Solution()
38+
input_list = ["sachin", "jose", "python", "learning", "leet", "code"]
39+
encode_str = s.encode(input_list)
40+
print(encode_str)
41+
print(s.decode(encode_str))

‎leetcode-master/arrays_and_hashing/group_anagrams.py

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
"""
2+
URL: https://leetcode.com/problems/group-anagrams/
3+
4+
"""
5+
from collections import defaultdict
6+
from typing import List
7+
8+
9+
# Solution 1:
10+
class Solution:
11+
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
12+
result = defaultdict(list)
13+
14+
for s in strs:
15+
count = [0] * 26
16+
for i in s:
17+
count[ord(i) - ord('a')] += 1
18+
result[tuple(count)].append(s)
19+
20+
return result.values()
21+
22+
23+
"""
24+
Runtime
25+
88 ms Beats 64.27% of users with Python3
26+
Memory
27+
22.37 MB Beats 13.37% of users with Python3
28+
"""
29+
30+
31+
# Solution 2: Failed approach
32+
class Solution2:
33+
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
34+
result = []
35+
seen = []
36+
for i in range(len(strs)):
37+
if strs[i] not in seen:
38+
anagram_list = [strs[i]]
39+
seen.append(strs[i])
40+
for j in range(1, len(strs)):
41+
if strs[j] not in seen and self.find_anagram(strs[i], strs[j]):
42+
anagram_list.append(strs[j])
43+
seen.append(strs[j])
44+
result.append(anagram_list)
45+
return result
46+
47+
def find_anagram(self, str1, str2):
48+
if len(str1) != len(str2):
49+
return False
50+
hash_map = {}
51+
for i in str1:
52+
if i in hash_map:
53+
hash_map[i] += 1
54+
else:
55+
hash_map[i] = 1
56+
57+
for i in str2:
58+
if i in hash_map and hash_map[i] >= 0:
59+
hash_map[i] -= 1
60+
else:
61+
return False
62+
return True

‎leetcode-master/arrays_and_hashing/longest_consecutive_number.py

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
"""
2+
URL: https://leetcode.com/problems/longest-consecutive-sequence/description/
3+
4+
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
5+
6+
You must write an algorithm that runs in O(n) time.
7+
8+
9+
10+
Example 1:
11+
12+
Input: nums = [100,4,200,1,3,2]
13+
Output: 4
14+
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
15+
Example 2:
16+
17+
Input: nums = [0,3,7,2,5,8,4,6,0,1]
18+
Output: 9
19+
"""
20+
21+
from typing import List
22+
class Solution:
23+
def longestConsecutive(self, nums: List[int]) -> int:
24+
number_set = set(nums)
25+
longest = 0
26+
27+
for num in nums:
28+
if (num-1) not in number_set:
29+
length = 0
30+
while (num + length) in number_set:
31+
length += 1
32+
longest = max(longest, length)
33+
34+
return longest
35+
36+
"""
37+
Runtime
38+
4246 ms Beats 28.35% of users with Python3
39+
Memory
40+
31.76 MB Beats 74.67% of users with Python3
41+
"""

‎leetcode-master/arrays_and_hashing/product_of_two_array.py

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
"""
2+
URL: https://leetcode.com/problems/product-of-array-except-self
3+
"""
4+
5+
from typing import List
6+
class Solution:
7+
def productExceptSelf(self, nums: List[int]) -> List[int]:
8+
9+
total_product = 1
10+
total_zeros = 0
11+
12+
for i in nums:
13+
if i != 0:
14+
total_product *= i
15+
else:
16+
total_zeros += 1
17+
18+
if total_zeros > 1:
19+
return [0] * len(nums)
20+
21+
result = []
22+
for num in nums:
23+
if num != 0:
24+
if total_zeros == 1:
25+
result.append(0)
26+
else:
27+
result.append(total_product // num)
28+
else:
29+
result.append(total_product)
30+
return result
31+
32+
"""
33+
34+
Runtime
35+
252 ms Beats 96.56% of users with Python3
36+
Memory
37+
25.56 MB Beats 94.32% of users with Python3
38+
"""

‎leetcode-master/arrays_and_hashing/top_k_elements.py

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
"""
2+
URL: https://leetcode.com/problems/top-k-frequent-elements/description/
3+
4+
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
5+
6+
7+
8+
Example 1:
9+
10+
Input: nums = [1,1,1,2,2,3], k = 2
11+
Output: [1,2]
12+
Example 2:
13+
14+
Input: nums = [1], k = 1
15+
Output: [1]
16+
17+
18+
Constraints:
19+
20+
1 <= nums.length <= 105
21+
-104 <= nums[i] <= 104
22+
k is in the range [1, the number of unique elements in the array].
23+
It is guaranteed that the answer is unique.
24+
25+
26+
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
27+
"""
28+
29+
from typing import List
30+
31+
32+
class Solution:
33+
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
34+
hash_map = {}
35+
freq = [[] for i in range(len(nums) + 1)]
36+
37+
for i in nums:
38+
hash_map[i] = hash_map.get(i, 0) + 1
39+
40+
result = []
41+
for key, value in hash_map.items():
42+
freq[value].append(key)
43+
44+
for i in range(len(freq) - 1, 0, -1):
45+
for n in freq[i]:
46+
result.append(n)
47+
if len(result) == k:
48+
return result
49+
50+
51+
"""
52+
Runtime
53+
91 ms Beats 44.40% of users with Python3
54+
Memory
55+
21.95 MB Beats 23.67% of users with Python3
56+
"""

0 commit comments

Comments
 (0)