DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Array Operations

The Hidden Cost of Array Operations

Index access and update are O(1) — that is well known. But insert and delete at arbitrary positions are O(n), and understanding why is what makes you a better programmer.

Because array elements are stored in contiguous memory, inserting or deleting at any position requires physically moving elements to maintain that contiguity. The computer cannot simply leave a gap or overlap elements — the layout must stay packed.

This page covers the mechanics of every core array operation: how the shifting actually works, when it is cheap, when it is expensive, and how to implement each operation correctly without bugs.

Operation 1: Insert

Inserting into an array means placing a new element at a specified position. The cost depends entirely on where you insert.

Insert at the End — O(1)

The cheapest insertion. No elements need to move. The new element lands at arr[length] and the length increments.

For dynamic arrays (ArrayList, Python list, C++ vector, JS array) this is O(1) amortized. For fixed-size arrays this is only possible if unused capacity remains.

Java

import java.util.ArrayList;
import java.util.List;

public class InsertAtEnd {

    public static void main(String[] args) {
        List<Integer> arr = new ArrayList<>();
        arr.add(10);
        arr.add(20);
        arr.add(30);

        System.out.println("Before: " + arr);

        // Insert at end — O(1) amortized, no shifting required
        arr.add(40);

        System.out.println("After adding 40: " + arr);
    }
}

Output:
Before: [10, 20, 30]
After adding 40: [10, 20, 30, 40]

Insert at an Arbitrary Index — O(n)

To insert at index k, every element from index k onward must shift one position to the right to make room. The further left you insert, the more elements shift.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class InsertAtIndex {

    // Insert value at index k in a fixed-size array (manual implementation)
    // Assumes arr has one extra slot at the end (size = current elements + 1)
    public static void insertAt(int[] arr, int currentSize, int k, int value) {
        // Shift elements from k onward one position to the right
        // Must go right to left to avoid overwriting
        for (int i = currentSize; i > k; i--) {
            arr[i] = arr[i - 1];
        }
        arr[k] = value;
    }

    public static void main(String[] args) {
        // Manual insert in a fixed array
        int[] arr = new int[7];
        arr[0] = 10; arr[1] = 20; arr[2] = 30; arr[3] = 40; arr[4] = 50;
        int size = 5;

        System.out.println("Before: " + Arrays.toString(Arrays.copyOf(arr, size)));

        // Insert 99 at index 2
        insertAt(arr, size, 2, 99);
        size++;

        System.out.println("After inserting 99 at index 2: "
            + Arrays.toString(Arrays.copyOf(arr, size)));

        // ArrayList handles shifting automatically
        List<Integer> list = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));
        list.add(2, 99); // index, value
        System.out.println("ArrayList insert at 2: " + list);
    }
}

Output:
Before: [10, 20, 30, 40, 50]
After inserting 99 at index 2: [10, 20, 99, 30, 40, 50]

Dry Run: Inserting 99 at Index 2 in [10, 20, 30, 40, 50]

Before:  [10, 20, 30, 40, 50, _ ]   (underscore = empty slot)
          0   1   2   3   4   5

Shifting right to left (must go right-to-left to avoid overwriting):
  i=5: arr[5] = arr[4] = 50  → [10, 20, 30, 40, 50, 50]
  i=4: arr[4] = arr[3] = 40  → [10, 20, 30, 40, 40, 50]
  i=3: arr[3] = arr[2] = 30  → [10, 20, 30, 30, 40, 50]
  i=2: stop (i == k)

Place new value:
  arr[2] = 99               → [10, 20, 99, 30, 40, 50]

Elements shifted: 3 (indices 2, 3, 4)
Cost: O(n) — proportional to how many elements are to the right of k

Insert at the Beginning — O(n)

The most expensive insertion — every single element must shift one position right.

Insert 99 at index 0 in [10, 20, 30, 40, 50]:

Before:  [10, 20, 30, 40, 50]

Shift every element right:
  50 → index 5
  40 → index 4
  30 → index 3
  20 → index 2
  10 → index 1

Place 99 at index 0:
After:   [99, 10, 20, 30, 40, 50]

Elements shifted: n (all of them)
Cost: O(n) — worst case for insertion

Operation 2: Delete

Deleting from an array means removing an element and closing the gap. Like insertion, the cost depends on where you delete.

Delete from the End — O(1)

Simply decrement the logical size. No elements move.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DeleteFromEnd {

    public static void main(String[] args) {
        List<Integer> arr = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));
        System.out.println("Before: " + arr);

        // Delete from end — O(1), no shifting
        int removed = arr.remove(arr.size() - 1);
        System.out.println("Removed: " + removed);
        System.out.println("After:   " + arr);
    }
}

Output:
Before: [10, 20, 30, 40, 50]
Removed: 50
After:   [10, 20, 30, 40]

Delete at an Arbitrary Index — O(n)

To delete at index k, every element after k shifts one position left to close the gap.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DeleteAtIndex {

    // Manual delete from fixed array — shows the shifting
    public static int deleteAt(int[] arr, int currentSize, int k) {
        int removed = arr[k];

        // Shift elements from k+1 onward one position to the left
        for (int i = k; i < currentSize - 1; i++) {
            arr[i] = arr[i + 1];
        }

        return removed; // Return the deleted value
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        int size = 5;

        System.out.println("Before: " + Arrays.toString(Arrays.copyOf(arr, size)));

        // Delete element at index 2
        int removed = deleteAt(arr, size, 2);
        size--;

        System.out.println("Removed: " + removed);
        System.out.println("After:   " + Arrays.toString(Arrays.copyOf(arr, size)));

        // ArrayList removes by index automatically
        List<Integer> list = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));
        int val = list.remove(2); // remove by index
        System.out.println("ArrayList remove at 2 → removed " + val + ": " + list);
    }
}

Output:
Before: [10, 20, 30, 40, 50]
Removed: 30
After:   [10, 20, 40, 50]

Dry Run: Deleting at Index 2 in [10, 20, 30, 40, 50]

Before: [10, 20, 30, 40, 50]
         0   1   2   3   4

Save removed = arr[2] = 30

Shifting left (go left to right to avoid overwriting):
  i=2: arr[2] = arr[3] = 40  → [10, 20, 40, 40, 50]
  i=3: arr[3] = arr[4] = 50  → [10, 20, 40, 50, 50]
  i=4: stop (i == size - 1)

Decrement size (or pop the last element):
After: [10, 20, 40, 50]   size = 4

Note the direction: INSERT shifts right-to-left.
                    DELETE shifts left-to-right.
Getting this wrong causes overwriting bugs.

Operation 3: Swap Two Elements

Swapping two elements is the atomic operation underlying sorting algorithms, partitioning, and in-place reversal. It requires a temporary variable — without one, you overwrite a value before saving it.

Java

public class SwapElements {

    // Swap elements at indices i and j
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i]; // Save arr[i] before overwriting
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};

        System.out.println("Before swap(1, 3): " + java.util.Arrays.toString(arr));
        swap(arr, 1, 3);
        System.out.println("After swap(1, 3):  " + java.util.Arrays.toString(arr));

        // Swapping first and last (useful in sorting and reversal)
        swap(arr, 0, arr.length - 1);
        System.out.println("After swap(0, 4):  " + java.util.Arrays.toString(arr));
    }
}

Output:
Before swap(1, 3): [10, 20, 30, 40, 50]
After swap(1, 3):  [10, 40, 30, 20, 50]
After swap(0, 4):  [50, 40, 30, 20, 10]

Operation 4: Reverse In-Place

Reversing an array in-place means reordering elements to the opposite sequence without allocating a new array. Use the two-pointer swap technique: one pointer at each end, swap and converge inward.

Java

public class ReverseArray {

    // Reverse array in-place — O(n) time, O(1) space
    public static void reverse(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            // Swap elements at left and right
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] odd  = {1, 2, 3, 4, 5};
        int[] even = {1, 2, 3, 4};
        int[] one  = {42};

        System.out.println("Before: " + java.util.Arrays.toString(odd));
        reverse(odd);
        System.out.println("After:  " + java.util.Arrays.toString(odd));

        reverse(even);
        System.out.println("Even reversed: " + java.util.Arrays.toString(even));

        reverse(one);
        System.out.println("Single:        " + java.util.Arrays.toString(one));
    }
}

Output:
Before: [1, 2, 3, 4, 5]
After:  [5, 4, 3, 2, 1]
Even reversed: [4, 3, 2, 1]
Single:        [42]

Dry Run: Reverse [1, 2, 3, 4, 5]

Array: [1, 2, 3, 4, 5]
        L           R

Step 1: swap arr[0]=1 and arr[4]=5 → [5, 2, 3, 4, 1]  L=1, R=3
Step 2: swap arr[1]=2 and arr[3]=4 → [5, 4, 3, 2, 1]  L=2, R=2
Step 3: L=2 >= R=2 → stop (middle element stays in place)

Result: [5, 4, 3, 2, 1]

Total swaps: n/2 (floor)
For n=5: 2 swaps
For n=4: 2 swaps
For n=1: 0 swaps (single element — loop never executes)

Operation 5: Rotate

Rotating an array shifts all elements left or right by k positions, with elements that fall off one end wrapping around to the other.

Rotate left by 2:   [1, 2, 3, 4, 5] → [3, 4, 5, 1, 2]
Rotate right by 2:  [1, 2, 3, 4, 5] → [4, 5, 1, 2, 3]

The elegant O(1) space approach uses three reversals: reverse the full array, then reverse each part.

Java

import java.util.Arrays;

public class RotateArray {

    private static void reverse(int[] arr, int left, int right) {
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    // Rotate right by k using three reversals — O(n) time, O(1) space
    public static void rotateRight(int[] arr, int k) {
        int n = arr.length;
        k = k % n; // Handle k >= n

        if (k == 0) return;

        reverse(arr, 0, n - 1);       // Reverse entire array
        reverse(arr, 0, k - 1);       // Reverse first k elements
        reverse(arr, k, n - 1);       // Reverse remaining n-k elements
    }

    // Rotate left by k — same as rotating right by (n - k)
    public static void rotateLeft(int[] arr, int k) {
        int n = arr.length;
        k = k % n;
        rotateRight(arr, n - k);
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        System.out.println("Original:       " + Arrays.toString(arr1));

        rotateRight(arr1, 2);
        System.out.println("Rotate right 2: " + Arrays.toString(arr1));

        int[] arr2 = {1, 2, 3, 4, 5};
        rotateLeft(arr2, 2);
        System.out.println("Rotate left  2: " + Arrays.toString(arr2));
    }
}

Output:
Original:       [1, 2, 3, 4, 5]
Rotate right 2: [4, 5, 1, 2, 3]
Rotate left  2: [3, 4, 5, 1, 2]

Dry Run: Rotate Right by 2 on [1, 2, 3, 4, 5]

n=5, k=2

Step 1 — Reverse entire array [0..4]:
  [1, 2, 3, 4, 5] → [5, 4, 3, 2, 1]

Step 2 — Reverse first k=2 elements [0..1]:
  [5, 4, 3, 2, 1] → [4, 5, 3, 2, 1]

Step 3 — Reverse remaining n-k=3 elements [2..4]:
  [4, 5, 3, 2, 1] → [4, 5, 1, 2, 3]

Result: [4, 5, 1, 2, 3]
Verify: elements 4,5 came from the right end and wrapped to the left ✓

Why three reversals work:
  The last k elements (4, 5) need to move to the front.
  Reversing the whole array puts them at the front but in wrong order.
  Reversing the first k fixes their order.
  Reversing the rest fixes the remaining elements' order.

Operation 6: Fill

Setting all or a range of elements to a specific value. Used for initialization, resetting, and setting up auxiliary arrays.

Java

import java.util.Arrays;

public class FillArray {

    public static void main(String[] args) {
        int[] arr = new int[6];

        // Fill entire array with a value
        Arrays.fill(arr, 7);
        System.out.println("Fill all with 7:    " + Arrays.toString(arr));

        // Fill a range [fromIndex, toIndex) — toIndex is exclusive
        Arrays.fill(arr, 2, 5, 99);
        System.out.println("Fill [2,5) with 99: " + Arrays.toString(arr));

        // Manual fill (shows the loop behind the built-in)
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i * 10;
        }
        System.out.println("Fill with i*10:     " + Arrays.toString(arr));
    }
}

Output:
Fill all with 7:    [7, 7, 7, 7, 7, 7]
Fill [2,5) with 99: [7, 7, 99, 99, 99, 7]
Fill with i*10:     [0, 10, 20, 30, 40, 50]

Operation Cost Summary

This table shows the actual cost of each operation depending on position. Understanding this table is essential for choosing between arrays and other data structures.

Operation	At End	At Index k	At Beginning
Insert	O(1) amortized	O(n) — shift n-k elements right	O(n) — shift all elements right
Delete	O(1)	O(n) — shift n-k-1 elements left	O(n) — shift all elements left
Access by index	O(1)	O(1)	O(1)
Update by index	O(1)	O(1)	O(1)
Swap two elements	O(1)	O(1)	O(1)
Reverse entire array	—	O(n) total	—
Rotate by k	—	O(n) total	—
Fill entire array	—	O(n) total	—

The pattern is clear: position-based access and update are always O(1). Position-based insert and delete at the middle or beginning are always O(n) because of the required shifting.

Common Mistakes Beginners Make

Shifting in the wrong direction during insert. When inserting at index k, you must shift elements right-to-left (starting from the end). Shifting left-to-right overwrites elements before they are saved, corrupting the array.

Shifting in the wrong direction during delete. When deleting at index k, you must shift elements left-to-right (starting from k). This is the opposite of insert.

Forgetting to handle k >= n in rotation. Rotating an array of 5 elements by 7 is the same as rotating by 2 (7 % 5 = 2). Always apply k = k % n before any rotation to handle this case. Without it, your reversal ranges will be out of bounds.

Swapping without a temporary variable. Without temp, you overwrite one value before reading it. In Java and C++, you need an explicit temp. Python's simultaneous assignment and JavaScript's destructuring avoid this, but the logic is identical underneath.

Off-by-one in partial operations. Java's Arrays.fill(arr, from, to, val) and Python's arr[from:to] use exclusive upper bounds — the element at index to is not filled. C++ fill(begin+from, begin+to, val) also uses exclusive end iterators. Always confirm whether the upper bound is inclusive or exclusive.

Interview Questions

Q: What is the time complexity of inserting at the beginning of an array, and why?

O(n). Every existing element must shift one position to the right to make room at index 0. In an array of n elements, that is n shifts — proportional to n. This is one of the core reasons arrays are not ideal when frequent front-insertion is needed. A linked list or deque inserts at the beginning in O(1).

Q: How do you rotate an array by k positions in O(1) space?

Use three in-place reversals: reverse the entire array, then reverse the first k elements, then reverse the remaining n-k elements. Each reversal is O(n) time and O(1) space. Always normalize k first with k = k % n to handle cases where k exceeds the array length.

Q: Why must you shift right-to-left when inserting and left-to-right when deleting?

When inserting at index k, you need to copy each element to its right neighbor. Starting from the right end ensures you copy to empty space, not over an element you still need. Starting from k and going right would overwrite arr[k+1] before copying it. For deletion, the opposite applies — you fill each gap from left to right, and starting from the left overwrites already-processed positions correctly.

Q: How do you reverse an array in-place without extra memory?

Use two-pointer swapping: initialize one pointer at index 0 (left) and one at index n-1 (right). Swap the elements they point to, then increment left and decrement right. Stop when left meets or crosses right. Total swaps: n/2. Time: O(n). Space: O(1).

FAQs

When should I use splice in JavaScript for deletion versus creating a new array?

Use splice when you need to modify the existing array in-place — it is O(n) but uses O(1) extra space. Use filter to create a new array without the element — it also runs in O(n) but allocates O(n) extra space. In interview problems where space efficiency matters, splice (in-place) is often preferred. In functional code where immutability is valued, filter is cleaner.

Does Python's list.insert(k, val) shift elements under the hood?

Yes. Python's list.insert() is O(n) in the worst case because CPython internally shifts all elements after index k one position to the right — the same shifting a manual implementation does. The operation looks like O(1) in Python code but the cost is still there. This is why repeated insertion at the beginning of a Python list is O(n²) total.

Is there a way to insert at the beginning of an array in O(1)?

Not for a static array or standard dynamic array — the contiguous memory layout requires shifting. If you frequently need O(1) insertion at the beginning, use a deque (double-ended queue), which maintains O(1) amortized insertion at both ends by using a chunked memory layout internally.

What happens to elements after the logical size when you delete from a fixed array?

The element at the old last position is still physically in memory — you just do not count it as part of the array anymore (by decrementing the logical size). The value sits there as dead data. This is fine as long as you only access indices within the logical size. Always use size to guard your loops rather than the allocated capacity.

Quick Quiz

Question 1: You want to insert an element at index 0 in an array of n elements. How many elements must shift?

›A) 0
›B) 1
›C) n/2
›D) n

Answer: D) n. Every element shifts one position right to make room at index 0. Index 0 insertion is the worst case for array insertion — all n elements must move.

Question 2: When deleting at index k from an array of n elements, in which direction must you shift elements, and why?

›A) Right to left — to avoid overwriting elements you still need
›B) Left to right — to fill each gap from the deleted position forward
›C) Either direction — the result is the same
›D) No shifting is needed

Answer: B) Left to right. You copy each element one position left to close the gap. Starting at k and working toward the end, arr[i] = arr[i+1] overwrites the gap with the next element. Going right-to-left would overwrite elements before they are used.

Question 3: An array has 8 elements. You rotate right by 11. What is the effective rotation?

›A) 11
›B) 3
›C) 5
›D) 8

Answer: B) 3. Effective rotation = 11 % 8 = 3. Rotating an 8-element array by 8 returns to the original. Rotating by 11 is the same as rotating by 3.

Question 4: What is the space complexity of reversing an array using two-pointer swapping?

›A) O(n) — a new reversed array is created
›B) O(log n) — recursion stack space
›C) O(1) — only two pointer variables and one temp variable are used
›D) O(n/2) — half the elements are copied

Answer: C) O(1). The two-pointer swap uses a constant number of extra variables (left, right, temp) regardless of array size. No new array is allocated. This is the definition of in-place — O(1) auxiliary space.

Summary

Array operations divide cleanly into two categories: those that use contiguous memory directly (O(1)) and those that must maintain contiguity by shifting (O(n)).

The key operations to carry forward:

›Insert at end — O(1) amortized, no shifting
›Insert at index k — O(n), shift right-to-left from end toward k
›Delete from end — O(1), just decrement size
›Delete at index k — O(n), shift left-to-right from k toward end
›Swap two elements — O(1), always needs a temp variable
›Reverse in-place — O(n) time, O(1) space, two-pointer swap converging inward
›Rotate by k — O(n) time, O(1) space, three-reversal technique with k = k % n
›Fill — O(n) time, O(1) space

In the next topic, you will explore Time and Space Complexity of Arrays — the full complexity analysis of every operation, and how constraints determine which operations are acceptable in interview solutions.

←

PreviousArray Traversal

NextTime & Space Complexity

→