100 Days of LeetCode Challenge: Day 3 — Tackling Duplicates, Single Elements, and Subsequences
Greetings, coding enthusiasts! 🌟
Embark on Day 3 of our LeetCode 100 Days Challenge, where we tackle the complexity duplicates, single elements and subsequences in coding problems. Today’s journey delves into the depths of sets, binary search, and string manipulation to strengthen our problem-solving skills.
Day 3 Highlights
1. Contains Duplicates
The Challenge: 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.
Example 1:
Input: nums = [1,2,3,1]
Output: trueOptimal Solution:
In addressing this challenge, we employ a set to track encountered elements. Through array iteration, we identify duplicate elements, enabling a swift determination of distinct or duplicate elements within the array.
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
encountered = set()
for num in nums:
if num in encountered:
return True
else:
encountered.add(num)
return False2. Single Element in a Sorted Array
The Challenge: You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space.
Example 1:
Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2Optimal Solution:
Utilizing binary search to maintain O(log n) time complexity, we strategically navigate through the sorted array to pinpoint the singularly occurring element.
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2 if mid % 2 == 1:
mid -= 1
if nums[mid] == nums[mid + 1]:
left = mid + 2
else:
right = mid
return nums[left]3. Append Characters to String to Make Subsequence
The Challenge: You are given two strings s and t consisting of only lowercase English letters.
Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
Example 1:
Input: s = "coaching", t = "coding"
Output: 4
Explanation: Append the characters "ding" to the end of s so that s = "coachingding".
Now, t is a subsequence of s ("coachingding").
It can be shown that appending any 3 characters to the end of s will never make t a subsequence.Optimal Solution:
Employing a two-pointer approach, we navigate through s and t to identify character matches, paving the way for efficient appendment calculations.
class Solution:
def appendCharacters(self, s: str, t: str) -> int:
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
else:
i += 1
return len(t) - jJoin the Challenge Journey:
Day 3 concludes with newfound insights and problem-solving prowess, setting the stage for further exploration as we navigate the LeetCode 100 Days Challenge alongside Ahmed Islam. Each day unveils unique learning opportunities, enriching our coding expertise. Stay tuned for more revelations and updates as we progress on this rewarding path.
For additional details and to connect with us, explore our social media channels:
Don’t miss out on enlightening coding content by following us on Medium. Let’s code and grow together! 🚀
