LeetCode Tutorial
26. Remove Duplicates from Sorted Array
Asked In :
Hello Friends Chai pe lo Chalo Choro,
Dekh bhai ye question h (Remove Duplicates from Sorted Array) Dekho is problem ma hame ek sorted array given hoga unha hame ek singel array ma sorted form ma store karna hai vo bhi without using extra space. or ha hame ye bhi batana hai ki kitne elements bace hai array ma.
Example 1:
Input: nums = [1,1,2] Output: 2, nums = [1,2,_] ---> array ma 2 element bache hai. Explanation: is ma 1 two times tha to ek 1 ko remove kr diya or last ma apna array return kr diya.
last ma kuch bhi bache hame us se matlab nhi hai.
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
class Solution {
public int removeDuplicates(int[] nums) {
int count=0; // store remaing elemet count
for(int i=0;i<nums.length;i++){
if(i<nums.length-1 && nums[i]==nums[i+1]){
continue;
}else {
nums[count]=nums[i];
count++;
}
}
return count;
}
}
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int i = 0;
for (const int num : nums)
if (i < 1 || num > nums[i - 1])
nums[i++] = num;
return i;
}
};
Dekh bhai phele toh hm ek function bna dege removeDuplicates naam ke agar num nhi hua to return zero kr dego.
Phir hm initialize kr dege k equal to 1. k denote krta h unique number bcoz first element always unique hota hai.
Phir hm for loop use krege aur starting from index 1 (for i in range(1, len(nums))). to end of element.
Phir hm if statement lagenge for check krege ke duplicate element present hai ke nhi. (nums[i]) from (nums[i - 1]). agar different hai to unique element hme mil gya.
Hm example leye hai to check the code.
Time complexity is O(n).
For More Information Visit To Our YouTube Channel [ Codgarage ].
def removeDuplicates(nums):
if not nums:
return 0
k = 1 # Initialize k to 1 since the first element is always unique
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
nums[k] = nums[i]
k += 1
return k
# Test cases
nums1 = [1, 1, 2]
result1 = removeDuplicates(nums1)
print(result1) # Output: 2
print(nums1[:result1]) # Output: [1, 2]
nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
result2 = removeDuplicates(nums2)
print(result2) # Output: 5
print(nums2[:result2]) # Output: [0, 1, 2, 3, 4]
Initialize Variables:
- Create an empty vector called ans to store unique elements.
- Create an empty map called mp to keep track of the frequency of each unique element.
Iterate Through the Input Vector (nums):
- Use a loop to iterate through each element of the input vector (nums).
- Inside the loop:
- Check if the current element (
nums[i]) is not present in the map (mp) or its frequency is zero. - If not present, add the element to the ans vector (to keep track of unique elements based on their first occurrence).
- Increment the frequency of the current element in the map.
- Check if the current element (
Update Input Vector (nums):
- Set the input vector (nums) equal to the ans vector. This overwrites the original vector with the vector containing unique elements.
Return Result:
- Return the size of the ans vector, which now represents the number of unique elements in the original vector.
import java.util.HashMap;
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
// Put elements in HashMap
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
// Search for the pair
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
int index = map.get(complement);
if (index == i) continue; // Ensure it's not the same element
return new int[]{index, i};
}
}
return new int[]{};
}
}
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
// Brute Force Solution
// Time O(NlogN) as map insertion takes O(logN) time and loop runs for N such iterations. Auxiliary Space O(N)
vector<int> ans;
map<int,int> mp;
for(int i = 0; i < nums.size() ; i++){
if(mp[nums[i]]==0)
ans.push_back(nums[i]); // ans vector stores unique elements based on their first occurence in nums vector
mp[nums[i]]++; // mp stores frequency of each unique element in nums vector
}
nums = ans; // ans vector has all unique elements in ascending order.
// These unique elements are overwritten on initial indices of nums array.
return ans.size();
}
};
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
numToIndex = {}
for i, num in enumerate(nums):
if target - num in numToIndex:
return numToIndex[target - num], i
numToIndex[num] = i
