BL
U

29. Delete Element in O(1) Without Preserving Order

Easy

Problem Description

Given an array of NN integers and an index idxidx, delete the element at index idxidx in O(1)O(1) time by overwriting it with the last element of the array and shrinking the size by 1.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers A0,…,AN−1A_0, \dots, A_{N-1}.
  • •Line 3: An integer idxidx (0≤idx<N0 \le idx < N).

Output Format

Print the N−1N-1 space-separated integers, or EMPTY if N=1N = 1.

Example 1:
Input:
5
10 20 30 40 50
1
Output:
10 50 30 40
Explanation: Element 20 at index 1 is replaced by last element 50.
Example 2:
Input:
1
7
0
Output:
EMPTY
Explanation: Removing the single element leaves EMPTY.
Example 3:
Input:
4
1 2 3 4
3
Output:
1 2 3
Explanation: Deleting the last element directly yields 1 2 3.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online