## algorithm to remove element from an array

May 2, 2013 1 Comment

This can be achieved in many ways, some of them are discussed here

– standard way when existing order is important: traverse through the elements, once element_to_be_deleted is found, shift remaining elements one position towards left. The **complexity of this algorithm is O(n)**

– when order of array is not important: take two pointers; one at the beginning of array and another at the end of the array. Increment the starting pointer till the element_to_be_deleted is found and decrement the ending pointer till element is not equals to element_to_be_deleted and then swap elements at start_pointer and end_pointer. The **complexity of this algorithm is O(n)**

– brute force algorithm. The **complexity of this algorithm is O(n*n)**

**standard way when existing order is important @ O(n)**

public int removeNumber(int[] a, int n) { if (a == null || a.length == 0) return -1; int i = 0; for (int j=0; j<a.length; j++) if (a[j] != n) a[i++] = a[j]; System.out.println("New size of the array is "+i); return i; // The new dimension of the array }

**when order of array is not important @ O(n)**

public void removeElementO_n(int[] a, int element) { int startPtr = 0; int endPtr = a.length-1; //{1,4,2,4,3,5,4,4}; while(startPtr < endPtr) { while(endPtr > 0 && a[endPtr] == element) { a[endPtr]=-1; endPtr--; } while(startPtr < a.length && a[startPtr] != element) { startPtr++; } if(startPtr < endPtr) { a[startPtr] = a[endPtr]; a[endPtr] = -1; startPtr++; endPtr--; } } }

**brute force algorithm @ O(n*n)**

public void removeElementO_n2(int[] a, int element) { int ct=0; int ln = a.length; //{1,4,2,4,3,5,4,4}; for (int i = 0; i < a.length; i++) { if(a[i] == element) { ct++; for (int j = i; j < a.length; j++) { if((j+1)<a.length) { a[j] = a[j+1]; } } a[ln-ct] = -1; } } }

## Recent Comments