Question

Describe how one can implement each of the following operations on an array so that the time it takes does not depend on the array’s size n.

a. Delete the $i$th element of an array ($1\leq i \leq n$).

b. Delete the $i$th element of a sorted array (the remaining array has to stay sorted).

Answer 1

Ans.

First of all I think "$i$th element" it should be i^th element so i'm answering it by considering as i^th

a).

For the first part best way to delete i^th element of a unsorted array of size n so that the time taken to delete it does not depend on the array’s size is swaping the i^th element with the (n-1)^th element (i.e last element) of given array and reduce the array size by 1.

b).

Best way to delete the i^th element of sorted array of size n so that the time taken to delete it does not depend on the array’s size is using "lazy deletion" i.e replacing the i^th element with a special symbol that cannot be a value of the array's element (eg., 0 for an array which hold the integer greater than 0) to mark the i^th position as empty.

This is done to indicate that the element does not belong to the array any more.