Insert, Delete, and Search an Element in an Array

Arrays are the first data structure every placement coding round tests, and insert, delete, and search are the three operations that appear most often.

Why Placement Rounds Focus on Array Operations

Arrays are not interesting because they are easy. They are interesting because they are unavoidable. Every compound data structure, from hash tables and heaps to adjacency matrices and queue implementations, relies on contiguous memory with index access. A candidate who cannot reason through a basic insert or delete operation, and give its time complexity in the same breath, signals a foundation that will not hold under harder problems.

Placement rounds at TCS, Infosys, Wipro, and Cognizant test these in their coding sections. Product-tier companies go further: state the complexity before writing the code, then explain the edge cases after. Array operations are standard in the technical coding rounds of most drives, including L&T’s fresher recruitment process, which tests data structure fundamentals before domain-specific knowledge.

Insert an Element at a Given Position

How It Works

Inserting element e at 1-indexed position pos in an array of n elements:

• Check bounds first: if pos < 1 or pos > n+1, reject as invalid input.
• Starting from index n-1, shift each element one position to the right, working down to index pos-1.
• Place e at index pos-1.
• The logical size of the array increases by one.

The time complexity is O(n) in the worst case (insert at position 1 shifts every element). Inserting at the end (pos = n+1) is O(1). Space overhead is O(1) because the shift happens in-place.

Worked Example

• Input: array [1, 2, 3, 4, 5], insert 10 at position 4
• Step 1: shift index 4 right: a[5] = a[4] gives [1, 2, 3, 4, 5, 5]
• Step 2: shift index 3 right: a[4] = a[3] gives [1, 2, 3, 4, 4, 5]
• Step 3: place 10 at index 3: a[3] = 10 gives [1, 2, 3, 10, 4, 5]
• Result: [1, 2, 3, 10, 4, 5]

C Code

#include <stdio.h>
#include <stdlib.h>

/*
 * Insert element e at 1-indexed position pos in array a of current size n.
 * Returns new size on success, -1 on invalid input.
 * Caller must allocate at least n+1 elements.
 */
int insert_at(int *a, int n, int pos, int e) {
    if (pos < 1 || pos > n + 1) {
        printf("Invalid position\n");
        return -1;
    }
    for (int i = n - 1; i >= pos - 1; i--) {
        a[i + 1] = a[i];
    }
    a[pos - 1] = e;
    return n + 1;
}

int main(void) {
    int n;
    scanf("%d", &n);
    int *a = (int *)malloc((n + 1) * sizeof(int)); /* +1 for the inserted element */
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int pos, e;
    scanf("%d %d", &pos, &e);
    int new_n = insert_at(a, n, pos, e);
    if (new_n > 0) {
        printf("Array after insertion:\n");
        for (int i = 0; i < new_n; i++) {
            printf("%d\n", a[i]);
        }
    }
    free(a);
    return 0;
}

Two differences from the standard textbook version are worth knowing. The function returns the new size instead of printing inside the function itself; mixing I/O with core logic is a design issue interviewers at product-tier companies notice. And malloc allocates n+1 elements upfront to leave room for the inserted element.

Delete an Element at a Given Position

How It Works

Deleting the element at 1-indexed position pos from an array of n elements:

• Check bounds: if pos < 1 or pos > n, reject as invalid input.
• Starting at index pos-1, overwrite each element with the element one position to its right, until index n-2.
• The logical size decreases by one. The element now at index n-1 is a stale duplicate and ignored.

The time complexity is O(n) in the worst case (delete at position 1). Deleting the last element is O(1). Space overhead is O(1).

Worked Example

• Input: array [1, 2, 3, 4, 5], delete at position 3
• Step 1: a[2] = a[3] gives [1, 2, 4, 4, 5]
• Step 2: a[3] = a[4] gives [1, 2, 4, 5, 5]
• Logical size is now 4; the second 5 at index 4 is ignored
• Result: [1, 2, 4, 5]

C Code

#include <stdio.h>
#include <stdlib.h>

/*
 * Delete element at 1-indexed position pos from array a of size n.
 * Returns new size on success, -1 on invalid input.
 */
int delete_at(int *a, int n, int pos) {
    if (pos < 1 || pos > n) {
        printf("Invalid position\n");
        return -1;
    }
    for (int i = pos - 1; i < n - 1; i++) {
        a[i] = a[i + 1];
    }
    return n - 1;
}

int main(void) {
    int n;
    scanf("%d", &n);
    int *a = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int pos;
    scanf("%d", &pos);
    int new_n = delete_at(a, n, pos);
    if (new_n >= 0) {
        printf("Array after deletion:\n");
        for (int i = 0; i < new_n; i++) {
            printf("%d\n", a[i]);
        }
    }
    free(a);
    return 0;
}

Search an Element in an Array

Two strategies apply depending on whether the array is sorted.

Linear Search

Scan left to right, comparing each element with the target. Stop on a match or after exhausting the array.

• Time complexity: O(n) worst case (target is last element or absent)
• Best case: O(1) when the target is at index 0
• Works on: any array, sorted or unsorted

#include <stdio.h>

/* Returns the 0-indexed position of target in array a, or -1 if not found. */
int linear_search(int *a, int n, int target) {
    for (int i = 0; i < n; i++) {
        if (a[i] == target) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    int n;
    scanf("%d", &n);
    int a[100];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int target;
    scanf("%d", &target);
    int idx = linear_search(a, n, target);
    if (idx >= 0) {
        printf("%d found at position %d\n", target, idx + 1);
    } else {
        printf("%d not present in the array\n", target);
    }
    return 0;
}

Binary Search

Halve the search space at each step by comparing the target with the middle element.

• Time complexity: O(log n)
• Best case: O(1) when the target is the middle element
• Prerequisite: array must be sorted in ascending order

#include <stdio.h>

/* Returns the 0-indexed position of target in sorted array a, or -1 if not found. */
int binary_search(int *a, int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; /* avoids integer overflow */
        if (a[mid] == target) return mid;
        else if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main(void) {
    int n;
    scanf("%d", &n);
    int a[100];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int target;
    scanf("%d", &target);
    int idx = binary_search(a, n, target);
    if (idx >= 0) {
        printf("%d found at position %d\n", target, idx + 1);
    } else {
        printf("%d not present in the array\n", target);
    }
    return 0;
}

The mid = low + (high - low) / 2 expression is a standard safeguard. Writing (low + high) / 2 works on small test inputs but overflows when low + high exceeds INT_MAX (defined in <limits.h>; see cppreference for the exact bound per platform). This is a known flag in product-tier technical interviews.

Time and Space Complexity Summary

Operation	Best Case	Worst Case	Space	Notes
Insert at position	O(1)	O(n)	O(1)	Best case: insert at end
Delete at position	O(1)	O(n)	O(1)	Best case: delete last element
Linear search	O(1)	O(n)	O(1)	Works on unsorted arrays
Binary search	O(1)	O(log n)	O(1)	Sorted array required

Java and Python Implementations

Placement coding rounds at product-tier companies accept Java or Python. The logic is identical to the C version; the syntax is more concise.

Java

import java.util.Arrays;

public class ArrayOps {

    /** Insert element e at 1-indexed position pos. Returns new array. */
    public static int[] insertAt(int[] a, int pos, int e) {
        int n = a.length;
        if (pos < 1 || pos > n + 1) {
            System.out.println("Invalid position");
            return a;
        }
        int[] result = new int[n + 1];
        System.arraycopy(a, 0, result, 0, pos - 1);
        result[pos - 1] = e;
        System.arraycopy(a, pos - 1, result, pos, n - pos + 1);
        return result;
    }

    /** Delete element at 1-indexed position pos. Returns new array. */
    public static int[] deleteAt(int[] a, int pos) {
        int n = a.length;
        if (pos < 1 || pos > n) {
            System.out.println("Invalid position");
            return a;
        }
        int[] result = new int[n - 1];
        System.arraycopy(a, 0, result, 0, pos - 1);
        System.arraycopy(a, pos, result, pos - 1, n - pos);
        return result;
    }

    /** Linear search. Returns 0-indexed position, or -1 if not found. */
    public static int linearSearch(int[] a, int target) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println("After insert: " + Arrays.toString(insertAt(arr, 4, 10)));
        System.out.println("After delete: " + Arrays.toString(deleteAt(arr, 3)));
        int idx = linearSearch(arr, 3);
        System.out.println("Search for 3: position " + (idx >= 0 ? idx + 1 : "not found"));
    }
}

Python

def insert_at(a, pos, e):
    """Insert element e at 1-indexed position pos. Returns new list."""
    if pos < 1 or pos > len(a) + 1:
        print("Invalid position")
        return a
    return a[:pos - 1] + [e] + a[pos - 1:]

def delete_at(a, pos):
    """Delete element at 1-indexed position pos. Returns new list."""
    if pos < 1 or pos > len(a):
        print("Invalid position")
        return a
    return a[:pos - 1] + a[pos:]

def linear_search(a, target):
    """Returns 0-indexed position of target, or -1 if not found."""
    for i, v in enumerate(a):
        if v == target:
            return i
    return -1

if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5]
    print("After insert:", insert_at(arr, 4, 10))
    print("After delete:", delete_at(arr, 3))
    idx = linear_search(arr, 3)
    print(f"Search for 3: position {idx + 1}" if idx >= 0 else "3 not found")

Python’s slice notation makes insert and delete one-liners. For service-tier placement rounds this is fine. For product-tier roles, writing the explicit loop that mirrors the shift mechanism demonstrates you understand what the slice abstracts.

Common Interview Variations

These four problems build directly on insert, delete, and search. Each reduces to the same shift mechanics once you see the structure:

• Rotate left by k positions: shift the first k elements out one at a time, re-inserting each at the end. Reduces to k calls to delete-at-position-1 followed by insert-at-end.
• Remove all duplicates from a sorted array: a single-pass scan with two index pointers (read and write). O(n) time, O(1) space. The write pointer advances only when the current element differs from the previous one.
• Find all occurrences of a target: same logic as linear search, but continue past the first match and collect every matching index.
• Insert into a sorted array: use binary search to locate the insertion index, then shift right. O(log n) to locate, O(n) to shift; the shift dominates.

A related array program that appears in the same placement context is Pascal’s triangle in C, which exercises 2D array indexing and row-by-row shift logic.

Practice Problems

Three problems in increasing difficulty, all solvable with the primitives above:

• Given two unsorted arrays of the same length, merge them into a single sorted array using only insert operations. Print the result.
• Write delete_all(a, n, val) that removes every occurrence of val in a single left-to-right pass using two index pointers (one to read, one to write). Return the new logical size.
• Given a sorted array of distinct integers, insert a new value such that the array stays sorted. Use binary search to find the insertion index, then shift right. State the time complexity before you write the code.

The third problem in particular combines the O(log n) search with the O(n) shift insert, which interviewers use to test whether you can reason about composite complexity.

For C coding practice across the full range of topics tested in TCS NQT, Infosys InfyTQ, and Wipro TalentNext, the C coding questions set covers the problems that appear most often.

---

Array insertion and deletion show up in every placement coding round, but the same shift-right and shift-left mechanics appear inside data pipelines, token buffers, and cache eviction policies in production systems. If you have wondered why AI language models drop context from the middle of a long prompt rather than the end, that is the O(n) cost of mid-sequence deletion you just studied. TinkerLLM starts at exactly that bridge, connecting the low-level array primitives to the AI system patterns built on them.