Problem-Solving Journey: Removing Duplicates from a Sorted Array
Aman Sharma
Student at ???????? ????CSE "26" |???? Web Dev| Front end developer | HTML|CSS|Javascript|??Reactjs|??Firebase
PAGE NO -1
Today, I worked on a problem-solving exercise that involves removing duplicates from a sorted integer array. Here's the problem and how I solved it.
?????????????? ??????????????????:
You are given a sorted integer array arr of size n. You need to remove the duplicates from this array, ensuring each element appears only once. The solution must modify the array in place without allocating extra space (O(1) extra memory).
??????????????:
**Input:**
n = 5, arr = [1, 2, 2, 2, 3]
**Output:**
[1, 2, 3]
The length of the new array is 3.
???? ????????????????:
To solve this, I used a two-pointer technique to iterate through the array and modify it in place. This approach ensures that we don’t use any extra memory, as required by the problem.
Here’s the code I wrote to solve the problem:
??★ C++ ★??
// ???????????????? ???? ???????????? ???????????????????? ???????? ?? ???????????? ??????????
int removeDuplicates(vector<int> &arr, int n) {
int i = 0; // ???????????????????? ?? ?????????????? '??' ???? ?????????? ?????? ???????????? ????????????????' ??????????????????
// ?????????? ?????????????? ???????? ?????? ???????????? ?????????????? (?????????? ??)
for (int j = 1; j < n; j++) {
// ???? ?????? ?????????????? ?????????????? ???? ?????????????????? ???????? ?????? ???????????????? ???????????? ??????????????
if (arr[i] != arr[j]) {
arr[i + 1] = arr[j]; // ???????? ?????? ???????????? ?????????????? ???? ?????? ???????? ????????????????
i++; // ?????????????????? '??' ???? ???????????? ?????? ???????????????? ???? ?????? ???????????? ??????????????
}
}
return i + 1; // ???????????? ?????? ?????? ???????????? ???? ?????? ?????????? (???????????? ???? ???????????? ????????????????)
}
???? ???????????? ???? ???? ???????? ???????? ???? ?????? ???????? ???????? :-
???????? ??????????????????????:
1. **Initialize pointer i:**
- This pointer will help us track where the next unique element should be placed.
2. **Loop through the array:**
- Starting from the second element (index 1), we compare each element with the last unique element (`arr[i]`).
领英推荐
3. **Check for duplicates:**
- If the current element arr[j] is different from the last unique element arr[i], we know it’s a new unique element.
- We place this unique element in the position right after i, and then increment i to keep track of the new unique array's length.
4. **Return the new length:**
- After processing all elements, we return i + 1, which represents the total number of unique elements in the modified array.
????????????????????:
This problem helped me understand how to efficiently modify arrays in place without using extra memory. The two-pointer approach ensures optimal time complexity and fulfills the problem's constraints.
Feel free to share your thoughts or ask any questions. Let's keep improving our problem-solving skills together!
PAGE NO- 2
?????????????? ?????????????????????? ???? ???????????????? ??????:
Imagine you have a box of toys, and some of the toys are the same. You want to make sure you only keep one of each toy, but you can't use another box or put the toys somewhere else. You need to rearrange them in the same box so that you only have one of each.
For example, let's say you have 5 toys:
[Car, Ball, Ball, Ball, Doll]
Your job is to make sure that you only keep one of each toy, so the new list of toys looks like this:
[Car, Ball, Doll]
Now you only have 3 toys, and there are no duplicates!
????????????????:
To solve this, you can look at each toy one by one. If the next toy is the same as the one you just saw, you skip it. But if the next toy is different, you keep it.
???????? ??????????????????????
Think of the code like this:
??★ C++ ★??
int removeDuplicates(vector<int> &arr, int n) {
int i = 0; // ?????????? ???????? ?????? ?????????? ??????
for (int j = 1; j < n; j++) { // ???????? ???? ?????? ???????????? ?????? ?????? ???????? ??????????
if (arr[i] != arr[j]) { // ???? ?????? ???????? ?????? ???? ??????????????????
arr[i + 1] = arr[j]; // ?????? ???? ???? ?????? ???????? ????????
i++; // ???????? ???? ?????? ???????? ???????? ?????? ?????? ???????? ???????????? ??????
}
}
return i + 1; // ???????????? ?????? ???????? ???????? ?????? ???????? ??????
}
???? ???????????? ??????????:
- You go through the toys one by one.
- If a toy is the same as the one you just saw, you ignore it.
- If it’s different, you put it in the box and keep counting how many unique toys you have.
---
This explanation uses toys and a box as examples to make it easier to understand removing duplicates from an array!