Given a sorted array arr of size N, the task is to reduce the array such that each element can appear at most two times.
Examples:
Input: arr[] = {1, 2, 2, 2, 3}
Output: {1, 2, 2, 3}
Explanation:
Remove 2 once, as it occurs more than 2 times.Input: arr[] = {3, 3, 3}
Output: {3, 3}
Explanation:
Remove 3 once, as it occurs more than 2 times.
Approach: This can be solved with the help of two pointer algorithm.
- Start traversing the array from the left and keep two pointers.
- One pointer (let’s say i) is used to iterate the array.
- And the second pointer (let’s say st) moves forward to find the next unique element. The element in i appears more than twice.
Below is the implementation of the above approach:
CPP
// C++ program to reduce the array// such that each element appears// at most 2 times#include <bits/stdc++.h>using namespace std;// Function to remove duplicatesvoid removeDuplicates(int arr[], int n){ // Initialise 2nd pointer int st = 0; // Iterate over the array for (int i = 0; i < n; i++) { if (i < n - 2 && arr[i] == arr[i + 1] && arr[i] == arr[i + 2]) continue; // Updating the 2nd pointer else { arr[st] = arr[i]; st++; } } cout << "{"; for (int i = 0; i < st; i++) { cout << arr[i]; if (i != st - 1) cout << ", "; } cout << "}";}// Driver codeint main(){ int arr[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call removeDuplicates(arr, n); return 0;} |
Java
// Java program to reduce the array// such that each element appears// at most 2 timesclass GFG{// Function to remove duplicatesstatic void removeDuplicates(int arr[], int n){ // Initialise 2nd pointer int st = 0; // Iterate over the array for (int i = 0; i < n; i++) { if (i < n - 2 && arr[i] == arr[i + 1] && arr[i] == arr[i + 2]) continue; // Updating the 2nd pointer else { arr[st] = arr[i]; st++; } } System.out.print("{"); for (int i = 0; i < st; i++) { System.out.print(arr[i]); if (i != st - 1) System.out.print(", "); } System.out.print("}");}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; int n = arr.length; // Function call removeDuplicates(arr, n);}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to reduce the array # such that each element appears # at most 2 times # Function to remove duplicates def removeDuplicates(arr, n) : # Initialise 2nd pointer st = 0; # Iterate over the array for i in range(n) : if (i < n - 2 and arr[i] == arr[i + 1] and arr[i] == arr[i + 2]) : continue; # Updating the 2nd pointer else : arr[st] = arr[i]; st += 1; print("{",end="") for i in range(st) : print(arr[i],end=""); if (i != st - 1) : print(", ",end=""); print("}",end=""); # Driver code if __name__ == "__main__" : arr = [ 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 ]; n = len(arr); # Function call removeDuplicates(arr, n); # This code is contributed by Yash_R |
C#
// C# program to reduce the array// such that each element appears// at most 2 timesusing System;class GFG{ // Function to remove duplicatesstatic void removeDuplicates(int []arr, int n){ // Initialise 2nd pointer int st = 0; // Iterate over the array for (int i = 0; i < n; i++) { if (i < n - 2 && arr[i] == arr[i + 1] && arr[i] == arr[i + 2]) continue; // Updating the 2nd pointer else { arr[st] = arr[i]; st++; } } Console.Write("{"); for (int i = 0; i < st; i++) { Console.Write(arr[i]); if (i != st - 1) Console.Write(", "); } Console.Write("}");} // Driver codepublic static void Main(String[] args){ int []arr = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; int n = arr.Length; // Function call removeDuplicates(arr, n);}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Java program to reduce the array// such that each element appears// at most 2 times// Function to remove duplicatesfunction removeDuplicates(arr,n){ // Initialise 2nd pointer let st = 0; // Iterate over the array for (let i = 0; i < n; i++) { if (i < n - 2 && arr[i] == arr[i + 1] && arr[i] == arr[i + 2]) continue; // Updating the 2nd pointer else { arr[st] = arr[i]; st++; } } document.write("{"); for (let i = 0; i < st; i++) { document.write(arr[i]); if (i != st - 1) document.write(", "); } document.write("}");}// Driver codelet arr = [ 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 ];let n = arr.length;// Function callremoveDuplicates(arr, n);// This code is contributed by sravan kumar</script> |
Output
{1, 1, 2, 2, 3, 3, 4, 5}
Time complexity: O(N)
Space complexity: O(1)
Another Approach: Using Counter() function
- Calculate the frequency of all elements using a counter function.
- Take an empty list.
- Traverse the array.
- If the frequency of any element is greater than or equal to 2, make its frequency 1 and append it to the list.
- If the frequency of any element is equal to 1, take its frequency 0 and append it to the list.
- Print the list.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;void removeDuplicates(int arr[],int n){ //unordered_map to store frequency unordered_map<int,int> mm; //this vector will contain the final elements form array vector<int> temp; //iterating over array to store frequency of each element for(int i=0;i<n;i++) { mm[arr[i]]++; } for(int i=0;i<n;i++) { //if a element is present 2 or more than 2 time than take this once and set //its frequenct to one which mean we have to take this element one time more if(mm[arr[i]]>=2) { temp.push_back(arr[i]); mm[arr[i]]=1; } else if(mm[arr[i]]==1) { temp.push_back(arr[i]); mm[arr[i]]=0; } } for(auto x:temp) { cout<<x<<" "; }}int main() { //array int arr[] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5}; //size of array int n = 14; // Function call removeDuplicates(arr, n);}//This code is contributed by shubhamrajput6156 |
Java
/*package whatever //do not write package name here */import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;class GFG { // Function to remove duplicatespublic static void removeDuplicates(int[] arr, int n) { // Taking empty list List<Integer> l = new ArrayList<>(); Map<Integer, Integer> freq = new HashMap<>(); for (int i = 0; i < n; i++) { if (freq.containsKey(arr[i])) { freq.put(arr[i], freq.get(arr[i]) + 1); } else { freq.put(arr[i], 1); } } for (int i = 0; i < n; i++) { if (freq.get(arr[i]) >= 2) { // Making frequency to 1 freq.put(arr[i], 1); l.add(arr[i]); } else if (freq.get(arr[i]) == 1) { // Making frequency to 0 // and appending to list l.add(arr[i]); freq.put(arr[i], 0); } } // Printing the list for (int i : l) { System.out.print(i + " "); }}// Driver codepublic static void main(String[] args) { int[] arr = {1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5}; int n = arr.length; // Function call removeDuplicates(arr, n);}} |
Python3
# Python3 program to reduce the array# such that each element appears# at most 2 timesfrom collections import Counter# Function to remove duplicatesdef removeDuplicates(arr, n): freq = Counter(arr) # Taking empty list l = [] for i in range(n): if(freq[arr[i]] >= 2): # Making frequency to 1 freq[arr[i]] = 1 l.append(arr[i]) elif(freq[arr[i]] == 1): # Making frequency to 0 # and appending to list l.append(arr[i]) freq[arr[i]] = 0 # Printing the list for i in l: print(i, end=" ")# Driver codeif __name__ == "__main__": arr = [1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5] n = len(arr) # Function call removeDuplicates(arr, n)# This code is contributed by vikkycirus |
C#
using System;using System.Collections.Generic;class Program{ static void RemoveDuplicates(int[] arr, int n) { // Dictionary to store frequency Dictionary<int, int> dict = new Dictionary<int, int>(); // This list will contain the final elements from array List<int> temp = new List<int>(); // Iterate over array to store frequency of each element for (int i = 0; i < n; i++) { if (dict.ContainsKey(arr[i])) dict[arr[i]]++; else dict.Add(arr[i], 1); } for (int i = 0; i < n; i++) { // If an element is present 2 or more than 2 times, take it once and set // its frequency to one, which means we have to take this element one time more if (dict[arr[i]] >= 2) { temp.Add(arr[i]); dict[arr[i]] = 1; } else if (dict[arr[i]] == 1) { temp.Add(arr[i]); dict[arr[i]] = 0; } } foreach (int x in temp) { Console.Write(x + " "); } } static void Main(string[] args) { // Array int[] arr = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; // Size of array int n = 14; // Function call RemoveDuplicates(arr, n); }}//This code is contributed by rudra1807raj |
Javascript
function removeDuplicates(arr, n) { // Create an object to store frequency of each element const freqMap = {}; // This array will contain the final elements from the input array const temp = []; // Iterate over the input array to store frequency of each element for (let i = 0; i < n; i++) { freqMap[arr[i]] = (freqMap[arr[i]] || 0) + 1; } // Iterate over the input array again to create a new array with unique elements for (let i = 0; i < n; i++) { // If an element is present more than once, take it once and set its frequency to 1 if (freqMap[arr[i]] >= 2) { temp.push(arr[i]); freqMap[arr[i]] = 1; } else if (freqMap[arr[i]] === 1) { // If an element is present only once, take it once and set its frequency to 0 temp.push(arr[i]); freqMap[arr[i]] = 0; } } // Print the new array with unique elements console.log(temp);}// Example usageconst arr = [1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5];removeDuplicates(arr, arr.length); |
Output
1 1 2 2 3 3 4 5
Time complexity: O(N)
Auxiliary Space: O(N)
Approach 3: Recursive Approach
1. Take a pointer j = 0 to keep track of the current position in the vector.
2. Iterate over the input vector using a pointer i.
3. If the current element is not a duplicate or appears at most two times, update it to the vector using the pointer j.
4. Increment the count of consecutive occurrences of the current element.
5. Recursively call the function with the next element in the vector.
6. Return the final value of the j to indicate the number of elements in the vector and then print the up to j elements which is our answer.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to remove duplicates from the vectorint removeDuplicates(vector<int>& arr, int n, int i, int j, int count) { // Base case: reached end of vector if (i == n) { return j; } // Count the consecutive occurrences of the current element if (i > 0 && arr[i] == arr[i - 1]) { count++; } else { count = 1; } // If the current element is not a duplicate or appears at most two times, // copy it to the output vector using the pointer j if (count <= 2) { arr[j] = arr[i]; j++; } // Recursively call the function with the next element in the input vector return removeDuplicates(arr, n, i + 1, j, count);}// Driver codeint main() { vector<int> arr = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; int n = arr.size(); // Function call int st = removeDuplicates(arr, n, 0, 0, 0); // Printing answer cout << "{"; for (int i = 0; i < st; i++) { cout << arr[i]; if (i != st - 1) cout << ", "; } cout << "}"; return 0;} |
Java
import java.util.*;public class Main { // Function to remove duplicates from the vector public static int removeDuplicates(ArrayList<Integer> arr, int n, int i, int j, int count) { // Base case: reached end of vector if (i == n) { return j; } // Count the consecutive occurrences of the current // element if (i > 0 && arr.get(i) == arr.get(i - 1)) { count++; } else { count = 1; } // If the current element is not a duplicate or // appears at most two times, copy it to the output // vector using the pointer j if (count <= 2) { arr.set(j, arr.get(i)); j++; } // Recursively call the function with the next // element in the input vector return removeDuplicates(arr, n, i + 1, j, count); } // Driver code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList( 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5)); int n = arr.size(); // Function call int st = removeDuplicates(arr, n, 0, 0, 0); // Printing answer System.out.print("{"); for (int i = 0; i < st; i++) { System.out.print(arr.get(i)); if (i != st - 1) System.out.print(", "); } System.out.print("}"); }} |
Python3
# Function to remove duplicatesdef remove_duplicates(arr, n, i, j, count): # Base case: reached end of vector if i == n: return j # Count the consecutive occurrences of the current element if i > 0 and arr[i] == arr[i - 1]: count += 1 else: count = 1 # If the current element is not a duplicate or appears at most two times, # copy it to the output vector using the pointer j if count <= 2: arr[j] = arr[i] j += 1 # Recursively call the function with the next element in the input vector return remove_duplicates(arr, n, i + 1, j, count)# Driver codearr = [1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5]n = len(arr)# Function callst = remove_duplicates(arr, n, 0, 0, 0)# Printing answerprint("[", end="")for i in range(st): print(arr[i], end="") if i != st - 1: print(", ", end="")print("]") |
C#
using System;using System.Collections.Generic;class Program { // Function to remove duplicates from a list, allowing // up to two occurrences of each element static List<int> RemoveDuplicates(List<int> list) { List<int> result = new List<int>(); int count = 0; foreach(int num in list) { if (result.Count == 0 || num != result[result.Count - 1]) { // If the result list is empty or the // current element is different from the // last element result.Add(num); // Add the current element // to the result list count = 1; // Reset the count to 1 for the // new element } else if (count < 2) { // If the current element is the same as the // last element and count is less than 2 result.Add(num); // Add the current element // to the result list count++; // Increment the count to track // consecutive occurrences } } return result; // Return the list with unique // elements (up to two occurrences // each) } static void Main() { List<int> numbers = new List<int>{ 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; List<int> uniqueList = RemoveDuplicates( numbers); // Call the RemoveDuplicates function Console.Write("{"); for (int i = 0; i < uniqueList.Count; i++) { Console.Write(uniqueList[i]); if (i < uniqueList.Count - 1) Console.Write(", "); } Console.WriteLine("}"); }} |
Javascript
// Function to remove duplicates from an array, allowing up to two occurrences of each elementfunction removeDuplicates(arr) { const result = []; // Initialize an empty array to store the unique elements let count = 0; // Initialize a count to keep track of consecutive occurrences for (const num of arr) { // Loop through each element in the input array if (result.length === 0 || num !== result[result.length - 1]) { // If the result array is empty or the current element is different from the last element result.push(num); // Add the current element to the result array count = 1; // Reset the count to 1 for the new element } else if (count < 2) { // If the current element is the same as the last element and count is less than 2 result.push(num); // Add the current element to the result array count++; // Increment the count to track consecutive occurrences } } return result; // Return the array with unique elements (up to two occurrences each)}const inputArray = [1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5];const uniqueArray = removeDuplicates(inputArray); // Call the removeDuplicates functionconsole.log(`[${uniqueArray.join(', ')}]`); // Print the unique array to the console |
Output
{1, 1, 2, 2, 3, 3, 4, 5}
Time complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
