Insertion at Xth Position Solution in C++/Java/Python/JS
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.
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++
// 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;
}
Java
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;
}
}
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] = valJavascript
// 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;
}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).