How can one delete an arbitrary element from an array (vector) in constant time if the order of elements does not matter?

If the order of elements in an array (vector) is not important, you can remove an arbitrary element in constant time by replacing the element to be removed with the last element of the array and then decreasing the size of the array by 1.

This avoids shifting all subsequent elements, which usually takes linear time.

Example in C++:

#include <vector>

void removeAt(std::vector<int>& vec, size_t index) {
    if (index >= vec.size()) return;
    vec[index] = vec.back(); // replace the element to be removed with the last
    vec.pop_back();          // remove the last element
}