Insert an Element at a Position
Solve this ProblemEasy10 min
Topics
BasicsArrays
Companies
TCSInfosysWipro
Given an array
nums, a position index and a value, return a new array with value inserted at index. Elements from that position onward move one place to the right. index may equal the length, meaning "add at the end".
Because an array's elements sit side by side in memory, making room in the middle means shiftingShifting ElementsMoving a run of elements one position along to open (or close) a gap. every later element. That makes insertion O(n) in the worst case, even when a built-in hides the loop — and it is why appending at the end is so much cheaper than inserting at the front.
Test Case 1:
Input:nums = [10, 20, 30], index = 1, value = 15
Output:[10, 15, 20, 30]
Explanation:15 takes index 1 and everything from 20 onward moves one place right.
Test Case 2:
Input:nums = [10, 20, 30], index = 3, value = 40
Output:[10, 20, 30, 40]
Explanation:index = length means "add at the end".
Constraints
- ◆
1 ≤ nums.length ≤ 1000 - ◆
0 ≤ index ≤ nums.length - ◆
-1000000 ≤ nums[i], value ≤ 1000000
Try the Dry Run
Approach & Solutions
Build a New Array Around the GapGood
Arrays have a fixed length, so create a new one with one extra slot. Copy elements before index to the same positions, elements from index onward to one position later, and put the new value into the gap at index.
Time
O(n)Space
O(n)Java
class Solution {
public int[] insertAt(int[] nums, int index, int value) {
int[] result = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
if (i < index) {
result[i] = nums[i];
} else {
result[i + 1] = nums[i];
}
}
result[index] = value;
return result;
}
}Built-in InsertOptimal
Growable lists have an insert operation: ArrayList.add(index, value) in Java, list.insert in Python, vector::insert in C++ and splice in JavaScript. They shift the later elements for you. In C, copy the two halves with memcpy around the new value.
Time
O(n)Space
O(n)Java
class Solution {
public int[] insertAt(int[] nums, int index, int value) {
List<Integer> list = new ArrayList<>();
for (int v : nums) {
list.add(v);
}
list.add(index, value);
return list.stream().mapToInt(Integer::intValue).toArray();
}
}