Leetcode with dani
前往频道在 Telegram
Join us and let's tackle leet code questions together: improve your problem-solving skills Preparing for coding interviews learning new algorithms and data structures connect with other coding enthusiasts
显示更多1 262
订阅者
+124 小时
无数据7 天
+730 天
帖子存档
1 262
people = {
'Alice': 30,
'Bob': 25,
'Charlie': 35,
'David': 20,
'Eve': 28
}1 262
Hey Coders! 👋
Today, let's dive into a classic challenge: 3Sum! 🎯
▎Problem Statement:
Given an integer array
nums, your task is to return all the unique triplets [nums[i], nums[j], nums[k]] such that:
• i ≠ j ≠ k
• nums[i] + nums[j] + nums[k] = 0
▎Example:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation:
• The triplet [-1, 0, 1] sums to zero.
• The triplet [-1, -1, 2] also sums to zero.
▎Constraints:
• 3 ≤ nums.length ≤ 3000
• -10⁵ ≤ nums[i] ≤ 10⁵
▎Approach:
1. Sorting: The array is sorted to make it easier to find the triplets.
2. Fixed Pointer: The outer loop fixes the first element of the triplet.
3. Two-pointer Technique: The inner loop uses two pointers to find the other two elements that sum up to zero with the fixed element.
4. Avoiding Duplicates: The code skips over duplicate elements to ensure that only unique triplets are added to the result.
▎Complexity Analysis:
• Time Complexity: O(n²)
• Space Complexity: O(1) (excluding the space required for the output)
▎Challenge:
Can you solve it with a time complexity of O(n²) ? 🤔
▎Hint:
Think about how you can reduce the problem to a two-sum problem after fixing one element.
▎Solution Code (Python):
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return result
1 262
▎🌟 Day 4 Coding Challenges: Solutions Explanations 🌟
Welcome to Day 4 of our coding journey! Today, we tackle some exciting problems that challenge our data structure skills. Let’s dive in!
---
▎🏗 Q1: Insert Delete GetRandom O(1)
▎Problem Statement:
Design a data structure that supports insert, remove, and getRandom operations in average O(1) time.
▎💡 Solution:
To achieve O(1) time complexity for all operations, we can employ a clever combination of a dynamic array and a hash map:
1. Dynamic Array: Stores elements, allowing for O(1) random access.
2. Hash Map: Tracks the indices of elements for O(1) insertion and deletion.
3. Removal Strategy: Swap the target element with the last element to avoid shifting.
▎🔍 Python Implementation:
import random
class RandomizedSet:
def __init__(self):
self.array = [] # For O(1) random access
self.indices = {} # Maps elements to their indices
def insert(self, val: int) -> bool:
if val in self.indices:
return False # Element already exists
self.indices[val] = len(self.array)
self.array.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.indices:
return False # Element does not exist
index = self.indices[val]
last_element = self.array[-1]
# Swap and remove
self.array[index] = last_element
self.indices[last_element] = index
self.array.pop()
del self.indices[val]
return True
def getRandom(self) -> int:
return random.choice(self.array)
randomizedSet = RandomizedSet()
print(randomizedSet.insert(1)) # True
print(randomizedSet.remove(2)) # False
print(randomizedSet.insert(2)) # True
print(randomizedSet.getRandom()) # Either 1 or 2
print(randomizedSet.remove(1)) # True
print(randomizedSet.insert(2)) # False
print(randomizedSet.getRandom()) # 2
[[winner, loser]], return two sorted lists:
1. Players with 0 losses.
2. Players with exactly 1 loss.
▎💡 Solution:
We can efficiently solve this using:
• A hash map to count losses.
• A set to track all players.
▎🔍 Python Implementation:
def findWinners(matches):
loss_counts = {}
players = set()
for winner, loser in matches:
players.add(winner)
players.add(loser)
loss_counts[loser] = loss_counts.get(loser, 0) + 1
zero_losses = sorted([player for player in players if loss_counts.get(player, 0) == 0])
one_loss = sorted([player for player in players if loss_counts.get(player, 0) == 1])
return [zero_losses, one_loss]
matches = [[1, 3], [2, 1], [4, 2], [5, 2]]
result = findWinners(matches)
print(result) # Output: [[4, 5], [1, 3]]
s = "abc" and indices = [0, 2, 1], return "acb".
▎💡 Solution:
We create a result array of the same length as s and place each character at its corresponding index from the indices array.
▎🔍 Python Implementation:
def restoreString(s, indices):
result = [''] * len(s)
for i, idx in enumerate(indices):
result[idx] = s[i]
return ''.join(result)
s = "codeleet"
indices = [4, 5, 6, 7, 0, 2, 1, 3]
result = restoreString(s, indices)
print(result) # Output: "leetcode"1 262
Certainly! Let's go through each problem and provide solutions with clear explanations.
---
### Day 4 Q1: Insert Delete GetRandom O(1)
#### Problem:
Design a data structure that supports
insert, remove, and getRandom operations in average O(1) time.
#### Solution:
To achieve O(1) time complexity for all operations, we can use the following approach:
1. Use a dynamic array (list) to store elements for O(1) random access.
2. Use a hash map to track the indices of elements in the array for O(1) insertion and deletion.
3. For removal, swap the target element with the last element in the array to avoid shifting elements.
Here is the Python implementation:
import random
class RandomizedSet:
def __init__(self):
self.array = [] # Store elements for O(1) random access
self.indices = {} # Map elements to their indices in the array
def insert(self, val: int) -> bool:
if val in self.indices:
return False # Element already exists
self.indices[val] = len(self.array)
self.array.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.indices:
return False # Element does not exist
index = self.indices[val]
last_element = self.array[-1]
# Swap the target element with the last element
self.array[index] = last_element
self.indices[last_element] = index
# Remove the last element from the array and the hash map
self.array.pop()
del self.indices[val]
return True
def getRandom(self) -> int:
return random.choice(self.array)randomizedSet = RandomizedSet()
print(randomizedSet.insert(1)) # True
print(randomizedSet.remove(2)) # False
print(randomizedSet.insert(2)) # True
print(randomizedSet.getRandom()) # Either 1 or 2
print(randomizedSet.remove(1)) # True
print(randomizedSet.insert(2)) # False
print(randomizedSet.getRandom()) # 2[winner, loser], return two lists:
1. Players with 0 losses.
2. Players with exactly 1 loss.
Both lists should be sorted in ascending order.
#### Solution:
We can solve this using:
1. A hash map to count the number of losses for each player.
2. A set to track all players (including winners who have 0 losses).
3. Filter players based on their loss counts and sort the results.
Here is the Python implementation:
def findWinners(matches):
loss_counts = {}
players = set()
for winner, loser in matches:
players.add(winner)
players.add(loser)
loss_counts[loser] = loss_counts.get(loser, 0) + 1
zero_losses = sorted([player for player in players if loss_counts.get(player, 0) == 0])
one_loss = sorted([player for player in players if loss_counts.get(player, 0) == 1])
return [zero_losses, one_loss]matches = [[1, 3], [2, 1], [4, 2], [5, 2]]
result = findWinners(matches)
print(result) # Output: [[4, 5], [1, 3]]s = "abc" and indices = [0, 2, 1], return "acb".
#### Solution:
We can create a result array of the same length as s and place each character at its corresponding index from the indices array. Finally, convert the array back to a string.
Here is the Python implementation:
def restoreString(s, indices):
result = [''] * len(s)
for i, idx in enumerate(indices):
result[idx] = s[i]
return ''.join(result)s = "codeleet"
indices = [4, 5, 6, 7, 0, 2, 1, 3]
result = restoreString(s, indices)
print(result) # Output: "leetcode"1 262
Day 5
🗓 Daily Challenge #1
🧩 Build Array from Permutation
Given an array nums, build a new array ans where ans[i] = nums[nums[i]] for every index i.
Can you solve it without extra space? (Hint: Think modulo!)
🔗 Problem Link:
📌 Difficulty: Easy
🏷 Tags: #Array #InPlace
💡 Let’s see your optimized solutions!
👉 Drop your approach in the comments!
📊 Problem Breakdown #2
🔄 Matrix Rotation Check
Given two n x n matrices, determine if one can be obtained by rotating the other 90°, 180°, or 270°.
How would you efficiently check all possible rotations?
🔗 Problem Link:
📌 Difficulty: Medium
🏷 Tags: #Matrix #Transpose
🤔 Think about transpose + reverse vs. brute force. Which is better?
👉 Share your code snippets!
🚀 Advanced Problem Alert!
🔢 Tuple with Same Product
Find the number of tuples (a, b, c, d) such that a*b = c*d where all elements are distinct.
Can you avoid an O(n⁴) solution? (Hint: Hash maps are your friend!)
🔗 Problem Link:
📌 Difficulty: Medium
🏷 Tags: #HashTable #Combinatorics
💥 Challenge: Optimize for large arrays!
👉 Post your best time complexity in the comments!
1 262
https://t.me/+axQMvWILZ505Yjlk
Check this channel; it's better to share good resources I find in a separate channel rather than posting them here. I post new resources that teach you full stack development, including HTML, CSS, JavaScript, Bootstrap, Node.js, React, Git, MongoDB, APIs, and more
1 262
Day 4 Q1
Insert Delete GetRandom O(1)
Link:
Difficulty: Medium
Problem Description:
Design a data structure that supports the following operations in average O(1) time—insert, remove, and getRandom.
insert(val): Inserts an item val into the set if not already present. Returns true if the item was successfully inserted.
remove(val): Removes an item val from the set if present. Returns true if the item existed and was removed.
getRandom(): Returns a random element from the current set of elements. Each element must have an equal probability of being returned.
Example:
Input:
["RandomizedSet", "insert", "remove", "insert", "getRandom"]
[[], [1], [2], [2], []]
Output:
[null, true, false, true, 1]
Day 4 Q2
Find Players With Zero or One Losses
Link:
Difficulty: Medium
Problem Description:
Given an array of match results where each match is represented as [winner, loser], identify two sorted lists:
The first list contains players who have not lost any matches.
The second list contains players who have lost exactly one match.
If a player lost more than once, they should not appear in either list.
Example:
Input: matches = [[2,3], [1,3], [5,4], [6,4]]
Output: [[1,2,6], [3,4]]
Day 4 Q3
Shuffle String
Link:
Difficulty: Easy
Problem Description:
You are given a string s and an integer array indices of the same length. The task is to build a new string by shuffling s such that the character at the i-th position moves to indices[i] in the resulting string.
Example:
Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
1 262
Problem: Find Words That Can Be Formed by Characters
Problem Link:
You are given an array of strings words and a string chars. A string is good if it can be formed by characters from chars (each character can only be used once). Return the sum of lengths of all good strings in words.
Example 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings "cat" and "hat" can be formed using the characters of chars, so the total length is 3 + 3 = 6.
Example 2:
Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings "hello" and "world" can be formed using the characters of chars, so the total length is 5 + 5 = 10.
Constraints:
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
words[i] and chars consist of lowercase English letters.
Challenge: Can you solve this problem efficiently? Try it out and share your approach!
1 262
Easy Problem: Two Sum (LeetCode #1)
Given an array of integers
nums and an integer target, return indices of the two numbers such that they add up to target.
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
nums, find the subarray with the largest sum, and return its sum.
Example:
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 Explanation: The subarray [4, -1, 2, 1] has the largest sum = 6.Constraints: - 1 <= nums.length <= 10^5 - -10^4 <= nums[i] <= 10^4 Hint: Use Kadane's Algorithm (Greedy/Sliding Window approach) to solve this efficiently! Practice here: LeetCode --- Medium Problem: Valid Parentheses (LeetCode #20) Given a string
s containing just the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid.
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
Example:
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Constraints:
- 1 <= s.length <= 10^4
- s consists of parentheses only '()[]{}'.
Hint: Use a stack to ensure proper matching of parentheses!
Practice here: LeetCode1 262
To solve this problem, we need to find all unique triplets in an array that sum to zero. The solution must avoid duplicate triplets and efficiently handle the input constraints.
Approach
Sort the Array: Sorting helps in efficiently finding triplets and avoiding duplicates by allowing us to skip over identical elements.
Iterate with a Fixed Element: For each element in the array (up to the third last element), treat it as the first element of the triplet.
Two-Pointer Technique: Use two pointers (left and right) to find the remaining two elements such that their sum with the fixed element equals zero. Adjust the pointers based on whether the current sum is less than or greater than zero.
Skip Duplicates: After finding a valid triplet, skip over any subsequent duplicate elements to avoid adding the same triplet multiple times.
def threeSum(nums):
res = []
nums.sort()
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # Skip duplicate elements for the first element of the triplet
left, right = i + 1, n - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
if current_sum == 0:
res.append([nums[i], nums[left], nums[right]])
# Skip duplicates for the second element
while left < right and nums[left] == nums[left + 1]:
left += 1
# Skip duplicates for the third element
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif current_sum < 0:
left += 1
else:
right -= 1
return res 1 262
Day2 Q3
167. Two Sum II - Input Array Is Sorted
Medium
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Constraints:
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.
Try
1 262
Day2 Q2
15. 3Sum
Medium
Hint
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
try
1 262
![class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place inste](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDACgcHiMeGSgjISMtKygwPGRBPDc3PHtYXUlkkYCZlo+AjIqgtObDoKrarYqMyP/L2u71////m8H////6/+b9//j/2wBDASstLTw1PHZBQXb4pYyl+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj/wAARCAAhACgDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwDWOM9SPwp34mkI560BMUALmkwPf86XFGKAIRboCOW/OipsUUC5UBIAJPAHehSGGQQR6g1Hc/8AHtL/ALh/lTLIk2qEnJOeT9TTtpcL62LFFFFIYUUUUARz/wCpf/dNMtP+PZPx/nRRVfZJ6k9FFFSUFFFFAH//2Q==)
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
r = len(nums)-1
while r>=1:
if nums[r] >nums[r-1]:
if r+1<len(nums) and nums[r+1] >nums[r-1]:
k = 2
while (r+k<len(nums) and nums[r+k] >nums[r-1]):
k+=1
k-=1
nums[r+k],nums[r-1]=nums[r-1],nums[r+k]
else:
nums[r],nums[r-1]=nums[r-1],nums[r]
break
else:
r -= 1
l = len(nums)-1
while l>r:
if nums[l] <nums[r]:
nums[l],nums[r] = nums[r],nums[l]
l-=1
r+=11 262
Day 2 Q1
31. Next Permutation
Medium
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]
Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]
Topics : Two pointer and Array
Submit
1 262
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
left = 0
right = len(height) - 1
left_max = right_max = 0
total = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
total += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
total += right_max - height[right]
right -= 1
return total
