15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Check that the position is from 0 through length and that length is below capacity. Shift each value from the last one down to that position one cell right, working from the end. Write the new value and increase length. The shift costs O(n - p) for position p: O(n) at the front, O(1) at the end.
| Valid insert position | 0 through length, inclusive (length means append) |
|---|---|
| Valid delete position | 0 through length - 1 |
| Insert shift direction | Right to left, from length - 1 down to position |
| Delete shift direction | Left to right, from position + 1 to length - 1 |
| Insert time at position p | O(n - p): O(n) at the front, O(1) at the end |
| Delete time at position p | O(n - p - 1): O(n) at the front, O(1) at the end |
An array has a fixed number of cells: its capacity. Only some cells currently hold logical values: its length.
For an array with capacity 5 and length 3:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Cell | 10 | 20 | 30 | _ | _ |
The array has three logical values, at indices 0 through length - 1.
Two position rules control these operations:
0 through length, inclusive.
length means append after the current final value.0 through length - 1.
Insertion also requires unused capacity. If length == capacity, no empty cell is available for an in-place insertion.
Use this array throughout:
[10, 20, 30]15 at position 1Before inserting, show both indices and cells:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 20 | 30 | _ | _ |
15 must occupy index 1.
Index 1 already holds 20, so the algorithm must make room.
The values currently at indices 1 and 2 must each move one cell to the right:
20 must move from index 1 to index 2.30 must move from index 2 to index 3.Start with 30, then move 20.
Copying 20 into index 2 first would overwrite 30 before copying it.
Insertion shifts right to left. Copy the last value first, then the one before it, so nothing is overwritten. Write the new value into the gap, then raise length from 3 to 4.
The occupied cells are [10, 20, 30, _, _], and length = 3.
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 20 | 30 | _ | _ |
Copy A[2] into A[3].
30 moves right by one cell.
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 20 | 30 | 30 | _ |
The old value at index 2 remains for now. The copy opens space for the next shift.
Copy A[1] into A[2].
20 moves right by one cell.
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 20 | 20 | 30 | _ |
Index 1 is ready for the inserted value.
Write 15 at index 1.
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 15 | 20 | 30 | _ |
The array now has four logical values.
length = 4
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 15 | 20 | 30 | _ |
The result is [10, 15, 20, 30].
Consider the insertion shift again.
The algorithm starts at the final occupied index and moves backward toward the insertion position. At each step, values already processed have been copied safely one cell right.
For example, after moving 30 from index 2 to index 3:
2 is safely at index 3.20 at index 1, has not been overwritten.The loop maintains this fact:
During a backward insertion shift from the end toward position
p, all elements originally at indices greater than the current source index have already been copied one position right, and their order is preserved.
That fact is the loop invariant.
Backward movement reads each source cell before a later write can overwrite it.
Deletion uses the opposite direction.
Suppose the logical array is [10, 15, 20, 30] and we delete position 1. The value 15 is removed logically, so values after it must close the gap:
20 from index 2 to index 1.30 from index 3 to index 2.The remaining values keep their order: [10, 20, 30].
To insert value at position:
position < 0 or position > length.length == capacity.length - 1.position.position.length.The shift runs from right to left:
1length - 1, length - 2, ..., positionWhen inserting 15 at position 1 with length 3, the source indices are:
12, 1Those indices produce the two copies:
1A[3] = A[2]
2A[2] = A[1]Then write:
1A[1] = 15To delete the value at position:
position < 0 or position >= length.position + 1, the first value after the deleted one.length.The deletion shift runs from left to right:
1position + 1, position + 2, ..., length - 1Each value is copied into the gap immediately before it.
The representation below stores:
values: the fixed-capacity backing arraylength: number of logical values currently storedcapacity: number of available cellsBoth operations mutate array.values and array.length only after their required checks pass.
1record FixedArray:
2 values // indexed cells 0 through capacity - 1
3 length // number of occupied logical cells
4 capacity // total number of cells in values1function insertAt(array: FixedArray, position: integer, value: integer) -> boolean
2 // Mutates array.values and array.length on success.
3 // Returns true on success.
4 // Returns false and makes no change when position is invalid
5 // or when the array has no unused capacity.
6
71. if position < 0 or position > array.length:
82. return false
9
103. if array.length == array.capacity:
114. return false
12
135. for source <- array.length - 1 down to position:
146. array.values[source + 1] <- array.values[source]
15
167. array.values[position] <- value
178. array.length <- array.length + 1
189. return trueThe loop includes position. The final copy moves the old value at position to position + 1, opening the target cell.
If position == length, the loop has no iterations. The target is already the first unoccupied cell.
1function deleteAt(array: FixedArray, position: integer) -> boolean
2 // Mutates array.values and array.length on success.
3 // Returns true on success.
4 // Returns false and makes no change when the array is empty
5 // or when position does not identify a logical value.
6
71. if array.length == 0:
82. return false
9
103. if position < 0 or position >= array.length:
114. return false
12
135. for source <- position + 1 to array.length - 1:
146. array.values[source - 1] <- array.values[source]
15
167. array.length <- array.length - 1
178. return trueAfter deletion, the former final occupied cell may still physically contain an old value. It is outside the logical array because length has decreased, so later operations must not treat it as a stored value.
Dry-run insertAt using the original example:
1capacity = 5
2length = 3
3values = [10, 20, 30, _, _]
4position = 1
5value = 151position < 0 or position > array.length
21 < 0 or 1 > 3
3false or false
4falseDo not return. Position 1 is valid.
1array.length == array.capacity
23 == 5
3falseDo not return. An empty cell is available.
The loop begins with:
1source = array.length - 1 = 2source = 2Line 6:
1array.values[3] <- array.values[2]State:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 20 | 30 | 30 | _ |
The next source index is 1.
source = 1Line 6:
1array.values[2] <- array.values[1]State:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 20 | 20 | 30 | _ |
The next source index would be 0, but 0 is less than position, which is 1. The loop stops.
1array.values[1] <- 15State:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 15 | 20 | 30 | _ |
1array.length <- 3 + 1Now:
1length = 41return trueThe final logical array is [10, 15, 20, 30].
Assume insertAt returns true.
Before the shift begins, the array has valid occupied cells from index 0 through length - 1, and there is room at index length because length < capacity.
Initialization.
Before the first loop iteration, no values have been shifted. The set of values originally beyond the current source index is empty. The insertion-shift invariant holds.
Preservation.
Suppose the invariant holds before processing source index i.
The value originally at index i is still available at A[i]. Values originally at indices greater than i have already been copied one cell right. Writing:
1A[i + 1] = A[i]moves the current source value right by one cell. It does not disturb the shifted values farther right. Their relative order remains the same.
After this copy, all values originally at indices greater than or equal to i have moved one cell right in their original order. The invariant holds for the next iteration.
Termination.
The loop ends after copying the old value at position to position + 1.
At that point:
position remains unchanged.position through length - 1 has moved right one cell.position is open.Writing the new value at position produces the required sequence. Increasing length makes the new final occupied cell part of the logical array.
Assume deleteAt returns true.
The position check guarantees that position identifies an existing logical value.
Before the loop, values before position do not move. The loop starts with the first successor, at position + 1.
Each iteration copies:
1A[source] to A[source - 1]The next remaining value fills the current gap. Since the loop proceeds from left to right, each source is read before any later iteration needs it.
When the loop ends:
position are unchanged.position has moved one cell left.Reducing length excludes the old final occupied cell from the logical array. Thus exactly the value at position is deleted.
Let n be the current length.
For insertion at position p, the loop shifts:
1n - pexisting values.
Then the algorithm performs:
Insertion takes O(n - p) time for the shift work, with constant additional work.
At the front, p = 0, so n values shift:
1O(n)At the end, p = n, so no existing values shift. The operation performs only the write and length update:
1O(1)For deletion at position p, the loop shifts:
1n - p - 1following values.
Then it performs one length update.
At position 0, the algorithm shifts n - 1 values, which is:
1O(n)At the final position, p = n - 1, so the shift count is:
1n - (n - 1) - 1 = 0No left shift occurs. Only the length update is needed:
1O(1)Both algorithms use a loop index and direct array assignments. They do not allocate another array.
Auxiliary space is:
1O(1)Incorrect loop direction:
1for source <- position to array.length - 1:
2 array.values[source + 1] <- array.values[source]Exposing input:
1[10, 20, 30], insert 15 at position 1Trace the wrong copies:
1A[2] <- A[1] // [10, 20, 20, _, _]
2A[3] <- A[2] // [10, 20, 20, 20, _]
3A[1] <- 15 // [10, 15, 20, 20, _]Wrong result:
1[10, 15, 20, 20]The original 30 was overwritten before it could move.
Correction:
1for source <- array.length - 1 down to position:
2 array.values[source + 1] <- array.values[source]Incorrect assumption:
1array.length <- array.length - 1
2for source <- position + 1 to array.length - 1:
3 array.values[source - 1] <- array.values[source]Exposing input:
1[1, 2, 3], delete position 0After reducing length from 3 to 2, the loop only copies:
1A[0] <- A[1]The logical result becomes:
1[2, 2]The original 3 was never copied into the logical array.
Correction: shift all original successors first, then reduce length.
1for source <- position + 1 to array.length - 1:
2 array.values[source - 1] <- array.values[source]
3array.length <- array.length - 1position == lengthIncorrect position rule:
1if position < 0 or position >= array.length:
2 return falseExposing input:
1[1, 2] with capacity 3, insert 9 at position 2Position 2 is valid because it is exactly the current length. It means append.
Wrong behavior: the valid insertion is rejected.
Correction:
1if position < 0 or position > array.length:
2 return false| Operation | Input | Expected logical result |
|---|---|---|
| Insert at front | Insert 9 at position 0 into [1, 2], capacity 3 | [9, 1, 2] |
| Append | Insert 9 at position 2 into [1, 2], capacity 3 | [1, 2, 9], with no shifts |
| Delete first | Delete position 0 from [1, 2, 3] | [2, 3] |
| Delete final | Delete position 2 from [1, 2, 3] | [1, 2], with no left shift |
| Insert when full | Insert into an array where length == capacity | Return failure, or grow only if the interface explicitly supports growth |
| Delete when empty | Delete from an array where length == 0 | Return failure |
Implement in-place insertAt and deleteAt for a fixed-capacity integer-array representation containing values, length, and capacity.
The tests check:
0 and at position length,1class FixedArray:
2 def __init__(self, values, capacity):
3 self.values = values + [0] * (capacity - len(values))
4 self.length = len(values)
5 self.capacity = capacity
6
7 def insert_at(self, position, value):
8 if position < 0 or position > self.length: # position == length means append
9 return False
10 if self.length == self.capacity:
11 return False
12 for source in range(self.length - 1, position - 1, -1): # right to left
13 self.values[source + 1] = self.values[source]
14 self.values[position] = value
15 self.length += 1
16 return True
17
18 def delete_at(self, position):
19 if self.length == 0 or position < 0 or position >= self.length:
20 return False
21 for source in range(position + 1, self.length): # left to right
22 self.values[source - 1] = self.values[source]
23 self.length -= 1 # shrink after shifting
24 return True
25
26 def logical(self):
27 return self.values[:self.length]
28
29a = FixedArray([10, 20, 30], 5)
30print("insert 15 at 1 ->", str(a.insert_at(1, 15)).lower(), a.logical())
31print("delete at 1 ->", str(a.delete_at(1)).lower(), a.logical())
32print("insert 9 at 4 ->", str(a.insert_at(4, 9)).lower(), a.logical())
33print("delete at 3 ->", str(a.delete_at(3)).lower(), a.logical())1import java.util.Arrays;
2
3public class Main {
4 static int[] values = {10, 20, 30, 0, 0};
5 static int length = 3;
6 static int capacity = 5;
7
8 static boolean insertAt(int position, int value) {
9 if (position < 0 || position > length) return false; // position == length means append
10 if (length == capacity) return false;
11 for (int source = length - 1; source >= position; source--) { // right to left
12 values[source + 1] = values[source];
13 }
14 values[position] = value;
15 length++;
16 return true;
17 }
18
19 static boolean deleteAt(int position) {
20 if (length == 0 || position < 0 || position >= length) return false;
21 for (int source = position + 1; source < length; source++) { // left to right
22 values[source - 1] = values[source];
23 }
24 length--; // shrink after shifting
25 return true;
26 }
27
28 static String logical() {
29 return Arrays.toString(Arrays.copyOf(values, length));
30 }
31
32 public static void main(String[] args) {
33 System.out.println("insert 15 at 1 -> " + insertAt(1, 15) + " " + logical());
34 System.out.println("delete at 1 -> " + deleteAt(1) + " " + logical());
35 System.out.println("insert 9 at 4 -> " + insertAt(4, 9) + " " + logical());
36 System.out.println("delete at 3 -> " + deleteAt(3) + " " + logical());
37 }
38}1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6struct FixedArray {
7 vector<int> values; // size() is the capacity
8 int length;
9};
10
11bool insertAt(FixedArray& a, int position, int value) {
12 if (position < 0 || position > a.length) return false; // position == length means append
13 if (a.length == (int)a.values.size()) return false;
14 for (int source = a.length - 1; source >= position; source--) { // right to left
15 a.values[source + 1] = a.values[source];
16 }
17 a.values[position] = value;
18 a.length++;
19 return true;
20}
21
22bool deleteAt(FixedArray& a, int position) {
23 if (a.length == 0 || position < 0 || position >= a.length) return false;
24 for (int source = position + 1; source < a.length; source++) { // left to right
25 a.values[source - 1] = a.values[source];
26 }
27 a.length--; // shrink after shifting
28 return true;
29}
30
31string logical(const FixedArray& a) {
32 string s = "[";
33 for (int i = 0; i < a.length; i++) s += (i ? ", " : "") + to_string(a.values[i]);
34 return s + "]";
35}
36
37int main() {
38 FixedArray a{{10, 20, 30, 0, 0}, 3};
39 bool ok = insertAt(a, 1, 15);
40 cout << "insert 15 at 1 -> " << (ok ? "true" : "false") << " " << logical(a) << "\n";
41 ok = deleteAt(a, 1);
42 cout << "delete at 1 -> " << (ok ? "true" : "false") << " " << logical(a) << "\n";
43 ok = insertAt(a, 4, 9);
44 cout << "insert 9 at 4 -> " << (ok ? "true" : "false") << " " << logical(a) << "\n";
45 ok = deleteAt(a, 3);
46 cout << "delete at 3 -> " << (ok ? "true" : "false") << " " << logical(a) << endl;
47}1const array = { values: [10, 20, 30, 0, 0], length: 3, capacity: 5 };
2
3function insertAt(a, position, value) {
4 if (position < 0 || position > a.length) return false; // position === length means append
5 if (a.length === a.capacity) return false;
6 for (let source = a.length - 1; source >= position; source--) { // right to left
7 a.values[source + 1] = a.values[source];
8 }
9 a.values[position] = value;
10 a.length++;
11 return true;
12}
13
14function deleteAt(a, position) {
15 if (a.length === 0 || position < 0 || position >= a.length) return false;
16 for (let source = position + 1; source < a.length; source++) { // left to right
17 a.values[source - 1] = a.values[source];
18 }
19 a.length--; // shrink after shifting
20 return true;
21}
22
23const logical = (a) => `[${a.values.slice(0, a.length).join(', ')}]`;
24console.log(`insert 15 at 1 -> ${insertAt(array, 1, 15)} ${logical(array)}`);
25console.log(`delete at 1 -> ${deleteAt(array, 1)} ${logical(array)}`);
26console.log(`insert 9 at 4 -> ${insertAt(array, 4, 9)} ${logical(array)}`);
27console.log(`delete at 3 -> ${deleteAt(array, 3)} ${logical(array)}`);Inserting at position p moves every value from p to the end one cell right, which is n - p moves. At the front that is all n values. The write and the length update add only constant work.
Deletion removes the value at a position by copying every later value one cell left, then reducing length. Deleting [10, 15, 20, 30] at position 1 moves 20 and 30 left and gives [10, 20, 30]. The old last cell keeps a stale value, but it is outside the length.
Each copy overwrites the cell to its right. Going left to right on [10, 20, 30] copies 20 over 30 first and loses it, giving [10, 15, 20, 20]. Going right to left reads every cell before it is overwritten.
A fixed-capacity array rejects the insert, because no empty cell exists. To support growth, allocate a larger array and copy the n existing values first, which is O(n), then insert as usual.
At position length no value sits to the right, so the shift loop runs zero times. Only the write and the length update remain, which is O(1). At position 0 every stored value must move.