Insert an adjacent duplicate for all occurrences of a given element

Given an array arr[] of size n and an integer k, the task is to insert a duplicate of k adjacent to its every occurrence. Keep array's original length same by removing the elements from the back.

Examples:  

Input: arr[] = [1, 0, 2, 3, 0, 4, 5, 0], K = 0 
Output: [1, 0, 0, 2, 3, 0, 0, 4]
Explanation: The given array [1, 0, 2, 3, 0, 4, 5, 0] is modified to [1, 0, 0, 2, 3, 0, 0, 4] after insertion of two 0's and truncation of two extra elements.

Input: arr[] = [7, 5, 8], K = 8 
Output: [7, 5, 8] 
Explanation: After inserting an adjacent 8 into the array, it got truncated to restore the original size of the array.  

[Naive Approach] - One by One Insert and Truncate - O(n^2) Time and O(n) Space

This problem can be solved by using built-in or library functions to insert element or remove element from the back. The idea is to traverse the array and insert a duplicate of K right next to it and then pop the last element.

#include <iostream> #include <vector> using namespace std; vector<int> duplicateK(vector<int> arr, int k) {  int n = arr.size();  for(int i = 0; i < n; i++) {  if(arr[i] == k) {    // Insert an adjacent k  arr.insert(arr.begin() + i + 1, k);  i++;    // Pop the last element  arr.pop_back();  }  }  return arr; } int main() {  vector<int> arr = { 1, 0, 2, 3, 0, 4, 5, 0 };  int k = 0;  vector<int> ans = duplicateK(arr, k);  for(int i = 0; i < ans.size(); i++)  cout << ans[i] << " ";  return 0; } 

import java.util.ArrayList; import java.util.Arrays; public class Main {  public static ArrayList<Integer> duplicateK(ArrayList<Integer> arr, int k) {  int n = arr.size();  for (int i = 0; i < n; i++) {  if (arr.get(i) == k) {  // Insert an adjacent k  arr.add(i + 1, k);  i++;  // Remove the last element  arr.remove(arr.size() - 1);  }  }  return arr;  }  public static void main(String[] args) {  ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 0, 2, 3, 0, 4, 5, 0));  int k = 0;  ArrayList<Integer> ans = duplicateK(arr, k);  for (int num : ans) {  System.out.print(num + " ");  }  } } 

def duplicateK(arr, k): n = len(arr) i = 0 while i < n: if arr[i] == k: # Insert an adjacent k arr.insert(i + 1, k) i += 1 # Pop the last element arr.pop() i += 1 n = len(arr) # Adjust the length as array is modified return arr arr = [1, 0, 2, 3, 0, 4, 5, 0] k = 0 ans = duplicateK(arr, k) print(ans) 

using System; using System.Collections.Generic; class Program {  static List<int> DuplicateK(List<int> arr, int k)  {  int n = arr.Count;  for (int i = 0; i < n; i++)  {  if (arr[i] == k)  {  // Insert an adjacent k  arr.Insert(i + 1, k);  i++;  // Remove the last element  arr.RemoveAt(arr.Count - 1);  }  }  return arr;  }  static void Main()  {  List<int> arr = new List<int> { 1, 0, 2, 3, 0, 4, 5, 0 };  int k = 0;  List<int> ans = DuplicateK(arr, k);  foreach (var num in ans)  {  Console.Write(num + " ");  }  } } 

function duplicateK(arr, k) {  let n = arr.length;  for (let i = 0; i < n; i++) {  if (arr[i] === k) {  // Insert an adjacent k  arr.splice(i + 1, 0, k);  i++;  // Pop the last element  arr.pop();  }  }  return arr; } let arr = [1, 0, 2, 3, 0, 4, 5, 0]; let k = 0; let ans = duplicateK(arr, k); console.log(ans); 

Output: 

1 0 0 2 3 0 0 4 

[Expected Approach] - Using Two Pointer Technique- O(n) Time and O(1) Space

This approach first counts how many times k appears and then create two pointers ( curr, write_idx) where the first one points to the last index of the current array and the second one points to the sum of last index and the count of k.

Then, starting from the last element, it copies each element to its new position and, if the element is k, places another k next to it. This avoids overwriting any elements that need to be preserved.

• Since each K needs to be updated with two K entries adjacent to each other, the array will increase in length by an amount equal to the number of K that are present in the original array arr[].
• Find the total number of K to know the number of last elements to be removed.
• Initialize a variable write_idx that will point to the index at the end of this imaginary array and another pointer curr at the end of the current array, which is arr[n-1].
• Iterate from the end and for each element we assume that we are copying the element to its current position, but copy only if the write_idx < N, and keep updating the write_idx each time. For an element with a value of zero, write it twice.

#include <bits/stdc++.h> using namespace std; vector<int> duplicateK(vector<int>& arr,int k) {  const int n = arr.size();  // Find the count of total number of k  int cnt = count(arr.begin(), arr.end(), k);  // Variable to store index where elements  // will be written in the final array  int write_idx = n + cnt - 1;  // Variable to point the current index  int curr = n - 1;  while (curr >= 0 && write_idx >= 0) {    // Keep the current element to its correct  // position, if that is within the size N  if (write_idx < n)  arr[write_idx] = arr[curr];  write_idx -= 1;  // Check if the current element is also  // k then again write its duplicate  if (arr[curr] == k) {  if (write_idx < n)  arr[write_idx] = k;  write_idx -= 1;  }  --curr;  }  return arr; } int main() {  vector<int> arr = { 1, 0, 2, 3, 0, 4, 5, 0 };  int k=0;  vector<int> ans = duplicateK(arr,k);  for (int i = 0; i < ans.size(); i++)  cout << ans[i] << " ";  return 0; } 

class GfG{ static int[] duplicateK(int []arr,int k) {    int n = arr.length;    // Find the count of  // total number of k  int cnt = count(arr, k);    // Variable to store index   // where elements will be   // written in the final array  int write_idx = n + cnt - 1;    // Variable to point the current index  int curr = n - 1;    while (curr >= 0 && write_idx >= 0)  {    // Keep the current element   // to its correctposition, if   // that is within the size N  if (write_idx < n)  arr[write_idx] = arr[curr];    write_idx -= 1;    // Check if the current element is also  // k then again write its duplicate  if (arr[curr] == k)  {  if (write_idx < n)  arr[write_idx] = k;    write_idx -= 1;  }  --curr;  }  return arr; } static int count(int []arr, int num) {  int ans = 0;  for(int i : arr)    if(i == num)  ans++;  return ans; } public static void main(String[] args) {  int []arr = { 1, 0, 2, 3, 0, 4, 5, 0 };  int k=0;  int []ans = duplicateK(arr,k);  for(int i = 0; i < ans.length; i++)  System.out.print(ans[i] + " "); } } 

def duplicate_k(arr, k): n = len(arr) # Find the count of total number of k cnt = arr.count(k) # Variable to store index where elements # will be written in the final array write_idx = n + cnt - 1 # Variable to point the current index curr = n - 1 while curr >= 0 and write_idx >= 0: # Keep the current element to its correct # position, if that is within the size n if write_idx < n: arr[write_idx] = arr[curr] write_idx -= 1 # Check if the current element is also # k then again write its duplicate if arr[curr] == k: if write_idx < n: arr[write_idx] = k write_idx -= 1 curr -= 1 return arr if __name__ == '__main__': arr = [1, 0, 2, 3, 0, 4, 5, 0] k = 0 ans = duplicate_k(arr, k) for i in ans: print(i, end=' ') 

using System; class GfG {  static int[] DuplicateK(int[] arr, int k)  {  int n = arr.Length;    // Find the count of total number of k  int cnt = Count(arr, k);    // Variable to store index where elements   // will be written in the final array  int writeIdx = n + cnt - 1;    // Variable to point the current index  int curr = n - 1;  while (curr >= 0 && writeIdx >= 0)  {  // Keep the current element to its correct   // position, if that is within the size N  if (writeIdx < n)  arr[writeIdx] = arr[curr];  writeIdx -= 1;    // Check if the current element is also   // k then again write its duplicate  if (arr[curr] == k)  {  if (writeIdx < n)  arr[writeIdx] = k;  writeIdx -= 1;  }  --curr;  }  return arr;  }  static int Count(int[] arr, int num)  {  int ans = 0;  foreach (int i in arr)  if (i == num)  ans++;  return ans;  }  public static void Main(string[] args)  {  int[] arr = { 1, 0, 2, 3, 0, 4, 5, 0 };  int k = 0;  int[] ans = DuplicateK(arr, k);  for (int i = 0; i < ans.Length; i++)  Console.Write(ans[i] + " ");  } } 

function duplicateK(arr, k) {  const n = arr.length;  // Find the count of total number of k  const cnt = arr.filter(x => x === k).length;  // Variable to store index where elements  // will be written in the final array  let write_idx = n + cnt - 1;  // Variable to point the current index  let curr = n - 1;  while (curr >= 0 && write_idx >= 0) {    // Keep the current element to its correct  // position, if that is within the size n  if (write_idx < n) {  arr[write_idx] = arr[curr];  }  write_idx -= 1;  // Check if the current element is also  // k then again write its duplicate  if (arr[curr] === k) {  if (write_idx < n) {  arr[write_idx] = k;  }  write_idx -= 1;  }  curr--;  }  return arr; } const arr = [1, 0, 2, 3, 0, 4, 5, 0]; const k = 0; const ans = duplicateK(arr, k); ans.forEach(num => console.log(num)); 

1 0 0 2 3 0 0 4