Array VI
In problem-solving, inserting an element at a specific position in a dataset is a fundamental operation that helps us manage dynamic data efficiently. Whether we are updating a list of tasks, inserting a new player into a ranking board, or adding an item to a specific location in memory, this task ensures the data remains in the desired order without loss. Let’s explore how to achieve this efficiently.
16. Given an array of N+1 size containing N elements we need to insert an element val at the Xth position (0-Based Indexing), shifting the existing elements to the right.
Example
Input: nums[7] = [3, 7, 11, 2, 1, 10, _ ], X = 3, val = 5
Output: [3, 7, 11, 5, 2, 1, 10]
Explanation: The element val = 5, is inserted at 3rd position from the front, and all the other elements are shifted one position to the right.
Input: nums[5] = [10, 20, 30, 40, _ ], X = 1, val = 100
Output: [10, 100, 20, 30, 40]
Explanation: The element val = 100 is inserted at the 1st position, and all other elements are shifted accordingly.
Intuition
Let’s say we have 4 friends sitting in a row for a movie, and a new friend wants to join the group and sit in the 2nd seat (index 1, because arrays start at 0). Everyone from the 2nd position onwards needs to move one seat to the right to make space for the new friend. Once the space is created, the new person can step into the seat. If no one moves, there’s no room for them to sit. This is exactly what we are doing in an array when inserting a new element. The "friends" are the elements of the array, and "shifting" means moving each element one position to the right to make space for the new element.
Let’s break down the entire approach step-by-step, addressing any doubts or concerns that might come up for someone new to this
How do we know if we can insert the new element at a specific position?
Imagine trying to seat someone in a row of chairs. If you try to put them in a chair that doesn't exist, they’ll just be left standing! Similarly, in an array, the position must be valid — meaning it must exist within the bounds of the current array.
In our case, the valid positions for insertion are between 0 and n (where n is the number of existing elements). If the position is less than 0 or greater than n, it's like trying to seat someone outside the row, which isn't possible.
So, Before doing anything, we need to check if the position X where we want to insert the new element is valid. If X is less than 0 or greater than n, it’s not possible to insert the element, so we print an error message.
Example: If our array has 5 elements, and we want to insert the new element at position 7, that’s not valid because the array only has positions from 0 to 5.
How do we create space for the new element?
To create space at position X, we need to shift all elements starting from the last one (at index n-1) to the right. We do this one by one, working backwards from the last element to the Xth position.
Let’s visualize this with a real-world example.
Imagine 4 people are sitting in a row: [10, 20, 30, 40, _ ]. If a new friend wants to sit at position X = 1, we have to ask everyone from the second person (index 1) onwards to move one seat to the right.
- The person at position 3 (who is sitting on the last seat) will move to position 4.
- The person at position 2 will move to position 3, and so on.
This process will leave a gap at position 1, where the new person can sit.
What if we want to insert val at the nth(last) index?
If the new friend wants to sit in the last seat (at index n), no one needs to move. Let’s say the new person wants to sit at position X = 4: [10, 20, 30, 40, _ ]
Since position 4 is already the last spot, no one has to move. The new person can simply sit down in that seat directly, and no shifting is needed.
This makes the insertion at the last position an easy operation where shifting is unnecessary.
Why do we move elements from the back to the front?
We move from the back because if we started shifting elements from the front, we would overwrite the values that still need to be shifted. By moving from the back, we avoid this problem.
Now that we have a gap, how do we actually insert the element?
Once the gap is created, the position X is now empty. We can directly insert the new element into that position by simply assigning it to the array at index X.
Example:
- We have [10, 20, 30, 40], and after shifting, the array looks like this: [10, _, 20, 30, 40].
- Now, we place the new element (say, 100) at position 1, so the array becomes [10, 100, 20, 30, 40].
Once we’ve inserted the new element and shifted all the other elements, we simply print the final array.
Approach
Step 1: Take an integer input n which represents the number of initial elements in the array (excluding the extra space).
Step 2: Create an array of size n + 1 to hold the original n elements and allow space for one new element to be inserted.
Step 3: Input the first n elements and store them in the array from index 0 to n - 1.
Step 4: Take two more inputs:
- X — the index at which the new element should be inserted
- val — the value to be inserted
Step 5: Shift all elements starting from the end of the filled portion of the array (index n - 1) to index X, one position to the right. This means:
- Element at n - 1 moves to n
- Element at n - 2 moves to n - 1
- ...
- Until the element at index X moves to index X + 1
Step 6: Insert the new element val at index X.
Step 7: Print the entire array from index 0 to n, which now contains n + 1 elements including the newly inserted one.
Dry Run
Input: nums[7] = [3, 7, 11, 2, 1, 10, _], X = 3, val = 5
Initial Setup:
- We are given n = 6 elements: [3, 7, 11, 2, 1, 10]
- The array has size 7, meaning one empty slot is available for insertion.
- We are to insert val = 5 at index X = 3
- Elements at index 3 and beyond will be shifted one position to the right
Step-by-step Shift (from end to X):
We start from index i = n = 6, and go backward:
- i = 6:
nums[6] = nums[5] → 10
Array becomes: [3, 7, 11, 2, 1, 10, 10] - i = 5:
nums[5] = nums[4] → 1
Array becomes: [3, 7, 11, 2, 1, 1, 10] - i = 4:
nums[4] = nums[3] → 2
Array becomes: [3, 7, 11, 2, 2, 1, 10]
Step to Insert the Value:
- Now insert val = 5 at index X = 3
nums[3] = 5
Final array becomes:
[3, 7, 11, 5, 2, 1, 10]
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to insert an element at a specific index in the array
void insertAtPosition(int nums[], int n, int X, int val) {
// Step 1: Shift elements one position to the right from the end to index X
for (int i = n; i > X; i--) {
nums[i] = nums[i - 1];
}
// Step 2: Insert the new value at index X
nums[X] = val;
}
int main() {
// Step 1: Input the size N (number of initial elements, excluding the extra space)
int n;
cin >> n;
// Step 2: Declare an array of size N+1 to accommodate one insertion
int nums[n + 1];
// Step 3: Input the initial N elements
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
// Step 4: Input index X and the value to be inserted
int X, val;
cin >> X >> val;
// Step 5: Perform the insertion
insertAtPosition(nums, n, X, val);
// Step 6: Print the final array after insertion
for (int i = 0; i <= n; i++) {
cout << nums[i] << " ";
}
return 0;
}
Java
import java.util.Scanner;
public class LearnYard {
// Function to insert an element at a specific index in the array
public static void insertAtPosition(int[] nums, int n, int X, int val) {
// Step 1: Shift elements one position to the right from the end to index X
for (int i = n; i > X; i--) {
nums[i] = nums[i - 1];
}
// Step 2: Insert the new value at index X
nums[X] = val;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Step 1: Input the size N (number of initial elements, excluding the extra space)
int n = sc.nextInt();
// Step 2: Declare an array of size N+1 to accommodate one insertion
int[] nums = new int[n + 1];
// Step 3: Input the initial N elements
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
// Step 4: Input index X and the value to be inserted
int X = sc.nextInt();
int val = sc.nextInt();
// Step 5: Perform the insertion
insertAtPosition(nums, n, X, val);
// Step 6: Print the final array after insertion
for (int i = 0; i <= n; i++) {
System.out.print(nums[i] + " ");
}
sc.close();
}
}
Python
# Function to insert an element at a specific index in the array
def insert_at_position(nums, n, X, val):
# Step 1: Shift elements one position to the right from the end to index X
for i in range(n, X, -1):
nums[i] = nums[i - 1]
# Step 2: Insert the new value at index X
nums[X] = val
# Step 1: Input the size N (number of initial elements, excluding the extra space)
n = int(input())
# Step 2: Declare an array of size N+1 to accommodate one insertion
nums = list(map(int, input().split()))
nums.append(0) # Add extra space at the end
# Step 3: Input index X and the value to be inserted
X, val = map(int, input().split())
# Step 4: Perform the insertion
insert_at_position(nums, n, X, val)
# Step 5: Print the final array after insertion
print(*nums)
Javascript
// Function to insert an element at a specific index in the array
function insertAtPosition(nums, n, X, val) {
// Step 1: Shift elements one position to the right from the end to index X
for (let i = n; i > X; i--) {
nums[i] = nums[i - 1];
}
// Step 2: Insert the new value at index X
nums[X] = val;
}
// Input reading (Node.js style)
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let inputLines = [];
rl.on('line', function (line) {
inputLines.push(line.trim());
if (inputLines.length === 3) {
rl.close();
}
});
rl.on('close', function () {
// Step 1: Input the size N
const n = parseInt(inputLines[0]);
// Step 2: Read array and add one empty slot
const nums = inputLines[1].split(' ').map(Number);
nums.push(0); // Add extra space
// Step 3: Read X and val
const [X, val] = inputLines[2].split(' ').map(Number);
// Step 4: Perform the insertion
insertAtPosition(nums, n, X, val);
// Step 5: Print the final array
console.log(nums.join(' '));
});
Time Complexity: O(n)
In the given code, we are shifting the elements of the array to the right starting from the end (n-1) to the position X. Each element that is to the right of the position X is moved one position to the right. This shifting process is the main contributor to the time complexity.
- Shifting elements: In the worst case, we insert at position 0, meaning we need to shift all n elements one position to the right. Therefore, this involves n shifts.
- Insertion: Inserting the new element val at position X takes constant time, O(1), since we just assign a value to an index.
Thus, the overall time complexity of the operation is O(n), where n is the number of elements in the array before the insertion.
Space Complexity: O(1)
Auxiliary Space Complexity: This refers to any extra space used by the algorithm that is independent of the input size.
In this case, the only additional space we use is for variables such as val, X, and n, which all take up constant space. These do not depend on the size of the array, so the auxiliary space complexity is O(1).
Total Space Complexity: This is the space required for both the input array and any auxiliary space used by the algorithm.
The input array nums[] is of size n+1 (since it is designed to have space for one more element). So, the space complexity required for the array itself is O(n).
Continuing from insertion, deletion is another essential operation in problem-solving that helps us remove irrelevant, outdated, or specific elements from a dataset while preserving its structure. Whether it's removing a completed task from a to-do list, eliminating a player from a game leaderboard, or deleting an entry from a memory block, this operation ensures the dataset stays clean and efficient. In the case of arrays, deleting an element at a given index requires shifting all subsequent elements to the left to fill the gap and maintain continuity.
17. Given an array of size N, delete the element at the Xth position, shifting the remaining elements to the left. After deletion, the size of the array reduces by one.
Example
Input: nums[6] = [10, 20, 30, 40, 50, 60], X = 2
Output: [10, 20, 40, 50, 60, _ ]
Explanation: The element at index 2 (value = 30) is removed, and all elements to the right are shifted one position to the left.
Input: nums[5] = [5, 15, 25, 35, 45], X = 4
Output: [5, 15, 25, 35, _ ]
Explanation: The element at index 4 (value = 45) is deleted, no shifting is necessary since it’s the last element.
Intuition
Let’s say we have a row of 6 friends sitting for a movie, and one friend decides to leave from the 3rd seat (index 2). After this friend leaves, everyone sitting to their right must shift one seat to the left to fill the gap. This ensures that no empty seats are left in the middle. In an array, this means removing an element and shifting the remaining elements to the left.
How do we know if we can delete an element from a specific position?
Imagine trying to ask someone to leave a row of seats, but that seat number doesn’t exist! In the same way, when working with an array, the position from which you want to delete an element must be valid. The valid positions range from 0 to N-1 (where N is the number of elements in the array).
So before doing anything, we need to check if the position X from which we want to delete an element is valid. If X is less than 0 or greater than or equal to N, it’s like asking someone who isn’t there to leave. In this case, we print an error message.
Example: If our array has 5 elements, and we want to delete the element at position 6, that’s not valid because the array only has positions from 0 to 4.
How do we shift the elements to the left?
After deleting the element at position X, we need to move all the elements to its right one position to the left. We start from the position X+1 and shift each element to the left until the end of the array. This ensures that no gaps are left in the array.
Example: Let’s say we have the array [10, 20, 30, 40, 50, 60] and we want to delete the element at position X=2. After removing the element at index 2 (which is 30), we shift the elements:
- The element at position 3 (40) moves to position 2.
- The element at position 4 (50) moves to position 3.
- The element at position 5 (60) moves to position 4.
The resulting array will look like this: [10, 20, 40, 50, 60, _].
Why do we move elements to the left?
We move the elements to the left because if we didn’t, there would be a gap in the middle of the array, which could lead to incorrect results when working with the array in the future. By shifting the elements, we maintain the integrity of the array’s structure.
What happens after the elements are shifted?
After shifting the elements, the size of the array reduces by one. The position at the end of the array remains empty, but we can ignore that for further operations. The resulting array is now one element smaller.
Example: For the array [10, 20, 30, 40, 50, 60], after deleting the element at index 2 and shifting, the array becomes [10, 20, 40, 50, 60, _].
What if we delete the last element?
If the friend who wants to leave is sitting in the last seat, no shifting is required because there’s no one to the right of them. Once they leave, the seat is simply left empty.
Example: Let’s say the array is [5, 15, 25, 35, 45] and the friend sitting in the last seat (index 4) leaves. In this case, the array simply becomes [5, 15, 25, 35, _]. No elements need to be shifted since 45 was the last element.
Approach
Step 1: Take an integer input n which represents the number of elements currently in the array.
Step 2: Create an array of size n to store the input elements.
Step 3: Input n elements and store them in the array from index 0 to n - 1.
Step 4: Take another integer input X, which represents the index of the element to be deleted.
Step 5: Shift all elements one position to the left starting from index X:
- Element at index X + 1 moves to index X
- Element at index X + 2 moves to index X + 1
- ...
- Until the element at index n - 1 moves to index n - 2
Step 6: Reduce the size of the array by 1 (i.e., update n = n - 1) since one element has been removed.
Step 7: Print the array from index 0 to n - 1, which now contains n elements after deletion.
Dry Run
Input:
- Array Size (n) = 6
- Array Elements: [10, 20, 30, 40, 50, 60]
- Index to Delete (X) = 2
Initial Array (Before Deletion):
Index: 0, 1, 2, 3, 4, 5
Elements: [10, 20, 30, 40, 50, 60]
We want to delete the element at index 2, which is 30.
Step-by-step Shifting to the Left:
We start shifting elements from index X = 2 to n - 2 = 4.
- i = 2:
nums[2] = nums[3] = 40
Array becomes: [10, 20, 40, 40, 50, 60] - i = 3:
nums[3] = nums[4] = 50
Array becomes: [10, 20, 40, 50, 50, 60] - i = 4:
nums[4] = nums[5] = 60
Array becomes: [10, 20, 40, 50, 60, 60]
Size Reduction:
Now we decrease the size of the array by 1:
New size (n) = 5
Final Array (After Deletion):
Index: 0 1 2 3 4 5
Elements: [10, 20, 40, 50, 60, _ ]
- The last element (index 5) is now considered unused.
- We can represent it with an underscore _.
Output: [10, 20, 40, 50, 60, _ ]
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to delete element at index X
void deleteElementAtIndex(int nums[], int &n, int X) {
// Shift elements to the left from index X
for (int i = X; i < n - 1; i++) {
nums[i] = nums[i + 1];
}
// Reduce the size by 1
n--;
}
int main() {
int n;
cin >> n;
int nums[n];
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int X;
cin >> X;
deleteElementAtIndex(nums, n, X);
// Print the modified array with one less element
for (int i = 0; i < n; i++) {
cout << nums[i] << " ";
}
// Optional: show unused space as _
cout << "_";
return 0;
}
Java
import java.util.Scanner;
public class Main {
// Function to delete element at index X
static void deleteElementAtIndex(int[] nums, int n, int X) {
// Shift elements to the left from index X
for (int i = X; i < n - 1; i++) {
nums[i] = nums[i + 1];
}
// Reduce the size by 1
n--;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int X = sc.nextInt();
sc.close();
deleteElementAtIndex(nums, n, X);
// Print the modified array with one less element
for (int i = 0; i < n - 1; i++) {
System.out.print(nums[i] + " ");
}
// Optional: show unused space as _
System.out.print("_");
}
}
Python
# Function to delete element at index X
def delete_element_at_index(nums, n, X):
# Shift elements to the left from index X
for i in range(X, n - 1):
nums[i] = nums[i + 1]
# Reduce the size by 1
n -= 1
return n
# Input
n = int(input())
nums = list(map(int, input().split()))
X = int(input())
n = delete_element_at_index(nums, n, X)
# Print the modified array with one less element
for i in range(n):
print(nums[i], end=" ")
# Optional: show unused space as _
print("_")
Javascript
// Function to delete element at index X
function deleteElementAtIndex(nums, n, X) {
// Shift elements to the left from index X
for (let i = X; i < n - 1; i++) {
nums[i] = nums[i + 1];
}
// Reduce the size by 1
return n - 1;
}
// Read input
const readline = require("readline").createInterface({
input: process.stdin,
output: process.stdout
});
readline.question("", (n) => {
n = parseInt(n);
readline.question("", (nums) => {
nums = nums.split(" ").map(Number);
readline.question("", (X) => {
X = parseInt(X);
n = deleteElementAtIndex(nums, n, X);
// Print the modified array with one less element
let result = "";
for (let i = 0; i < n; i++) {
result += nums[i] + " ";
}
// Optional: show unused space as _
console.log(result + "_");
readline.close();
});
});
});
Time Complexity: O(n)
In the given deletion operation, we are shifting the elements of the array to the left starting from the position X+1 to the last position (n-1). Each element that is to the right of the position X is moved one position to the left. This shifting process is the primary contributor to the time complexity.
- Shifting Elements: In the worst case, we delete the element at position 0, meaning we need to shift all n−1 elements one position to the left. Therefore, this involves n-1 shifts.
- Deletion: Deleting the element at position X takes constant time, O(1), since we just remove the element from the array by shifting the elements to the left.
Thus, the overall time complexity of the deletion operation is O(n), where n is the number of elements in the array before the deletion.
Space Complexity: O(1)
Auxiliary Space Complexity: This refers to any extra space used by the algorithm that is independent of the input size. In this case, the only additional space we use is for variables such as X and n, which all take up constant space. These variables do not depend on the size of the array, so the auxiliary space complexity is O(1).
Total Space Complexity: This includes the space required for the input array and any additional space used by the algorithm.The input array nums[] is of size n, so the space complexity required for the array itself is O(n).
Thus, the overall space complexity is O(n), and the auxiliary space complexity is O(1).