Given an array arr consisting of N integers and an integer K, the task is to insert an adjacent K for every occurrence of it in the original sequence and then truncate the array to the original length using an O(1) auxiliary space.
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 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.
Approach 1: Using STL functions
This problem can be solved by using built-in functions pop_back() and insert() .
Below is the implementation of the above approach:
C++14
// C++ implementation to update each entry of k// with two k entries adjacent to each other#include <bits/stdc++.h>using namespace std;// Function to update each entry of k// with two k entries adjacent to each othervoid 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(); } }}// Driver codeint main(int argc, char* argv[]){ vector<int> arr= { 1, 0, 2, 3, 0, 4, 5, 0 }; int k=0; duplicateK(arr,k); for (int i = 0; i < arr.size(); i++) cout << arr[i] << " "; return 0;} |
Java
// Java implementation to update each // entry of k with two k entries// adjacent to each otherimport java.util.*;class GFG{// Function to update each entry of// k with two k entries // adjacent to each otherstatic Vector<Integer> duplicateK(Vector<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++; // Pop the last element arr.remove(arr.size() - 1); } } return arr;}// Driver codepublic static void main(String[] args){ Integer []arr = { 1, 0, 2, 3, 0, 4, 5, 0 }; Vector<Integer> vec = new Vector<Integer>();; for(int i = 0; i < arr.length; i++) vec.add(arr[i]); int k=0; Vector<Integer> ans = duplicateK(vec,k); for(int i = 0; i < ans.size(); i++) System.out.print(ans.get(i) + " ");}}// This code is contributed by gauravrajput1 |
Python3
# python3 implementation to update each entry of k# with two k entries adjacent to each other# Function to update each entry of k# with two k entries adjacent to each otherdef 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# Driver codeif __name__ == "__main__": arr = [1, 0, 2, 3, 0, 4, 5, 0] k = 0 duplicateK(arr, k) for i in range(0, len(arr)): print(arr[i], end=" ") # This code is contributed by rakeshsahni |
C#
// C# implementation to update each // entry of k with two k entries// adjacent to each otherusing System;using System.Collections.Generic;class GFG{// Function to update each entry of// k with two k entries // adjacent to each otherstatic 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++; // Pop the last element arr.RemoveAt(arr.Count - 1); } } return arr;}// Driver codepublic static void Main(String[] args){ int []arr = { 1, 0, 2, 3, 0, 4, 5, 0 }; int k=0; List<int> vec = new List<int>();; for(int i = 0; i < arr.Length; i++) vec.Add(arr[i]); List<int> ans = duplicateK(vec,k); for(int i = 0; i < ans.Count; i++) Console.Write(ans[i] + " ");}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript implementation to update each entry of k// with two k entries adjacent to each other// Function to update each entry of k// with two k entries adjacent to each otherfunction duplicateK(arr,k){ var N = arr.length; for(var 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;}// Driver codevar arr=[ 1, 0, 2, 3, 0, 4, 5, 0 ];var k=0;var ans = duplicateK(arr,k);for (var i = 0; i < ans.length; i++) document.write(ans[i] + " ");</script> |
Output:
1 0 0 2 3 0 0 4
Approach 2: Using Two Pointer Technique
- 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, then we assume we have an array with enough space to accommodate every element.
- 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.
Below is the implementation of the above approach:
C++14
// C++ implementation to update each entry of k// with two k entries adjacent to each other#include <bits/stdc++.h>using namespace std;// Function to update each entry of k// with two k entries adjacent to each othervector<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 the final result return arr;}// Driver codeint main(int argc, char* argv[]){ 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;} |
Java
// Java implementation to update // each entry of k with two k // entries adjacent to each otherclass GFG{// Function to update each // entry of k with two k // entries adjacent to each otherstatic 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 the final result return arr;}static int count(int []arr, int num){ int ans = 0; for(int i : arr) if(i == num) ans++; return ans;}// Driver codepublic 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] + " ");}}// This code is contributed by Amit Katiyar |
Python3
# Python3 implementation to update each entry of k # with two k entries adjacent to each other # Function to update each entry of k # with two k entries adjacent to each other def duplicateK(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 the final result return arr # Driver Code arr = [ 1, 0, 2, 3, 0, 4, 5, 0 ]k=0ans = duplicateK(arr,k) for i in range(len(ans)): print(ans[i], end = " ") # This code is contributed by divyamohan123 |
C#
// C# implementation to update // each entry of k with two k // entries adjacent to each otherusing System;class GFG{// Function to update each // entry of k with two k// entries adjacent to each otherstatic 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 readonly 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 the readonly result return arr;}static int count(int []arr, int num){ int ans = 0; foreach(int i in arr) { if(i == num) ans++; } return ans;}// Driver codepublic 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] + " ");}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript implementation to update each entry of k// with two k entries adjacent to each other// Function to update each entry of k// with two k entries adjacent to each otherfunction duplicateK(arr,k){ const N = arr.length; // Find the count of total number of k let cnt = 0; for(let i = 0; i < arr.length; ++i){ if(arr[i] == k) cnt++; } // 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 the final result return arr;}// Driver code let arr = [ 1, 0, 2, 3, 0, 4, 5, 0 ]; let k=0; let ans = duplicateK(arr,k); for (let i = 0; i < ans.length; i++) document.write(ans[i] + " ");// This code is contributed by Surbhi Tyagi.</script> |
Output:
1 0 0 2 3 0 0 4
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!
