Deletion at Xth Position
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.
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++
// 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--;
}Java
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--;
}
}
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 nTime 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).