The Kite of Success

Get unique elements in a sorted array

I/P – [1, 1, 1, 2, 3, 4, 5, 5]

O/P – [1, 2, 3, 4, 5]

Algorithm

array = [1, 1, 1, 2, 3, 4, 5, 5]

// In most of the programming language array index starts with 0
// Assume first element is unique in the array, so initialize index
// of uniqueElement
uniqueElementsCount = 1

// Start iterating the array from 2nd element
index = 1
while (index < arrayLength) {
	// If current element is not equal to previous element
	// then the current element is unique
	// Assign the current element to the last index of unique elements
	if(array[index] != array[index - 1]) {
		array[uniqueElementsCount] = array[index];
		uniqueElementsCount = uniqueElementsCount + 1;
	}
}

print "Showing unique numbers";
// uniqueElementsCount is count of unique elements in the same array
// Print unique array elements considering unique elements count
for(i = 0; i < uniqueElementsCount; i++) {
	print array[i]
}

Explanation

Code Implementation

public class UniqueElementsInAArray {

    /**
     * Time complexity - O(N)
     * Auxiliary Space complexity - O(1)
     * */
    public int getUniqueElementsInArray(int[] array) {
        // A corner case - Check if passed array data is empty or null
        if (array == null || array.length == 0) {
            // Return length as 0
            return 0;
        }

        // Assume first element is unique in the array, so initialize index
        // of uniqueElement
        int uniqueElementsCount = 1;

        // Iterate array from 2nd element
        for (int i = 1; i < array.length; i++) {
            // If current element is not equal to previous element, then it is unique
            if (array[i] != array[i - 1]) {
                array[uniqueElementsCount++] = array[i];
            }
        }

        return uniqueElementsCount;
    }

    public static void main(String[] args) {
        UniqueElementsInAArray uniqueElementsInAArray = new UniqueElementsInAArray();

        int[] input = {1, 2};
        int lastUniqueElementIndex = uniqueElementsInAArray.getUniqueElementsInArray(input);

        // Printing unique elements, sperepated with spaces
        for (int i = 0; i < lastUniqueElementIndex; i++) {
            System.out.print(input[i] + " ");
        }
    }
}
function uniquElementsInArray(elementsArray) {
    // Corner case - Check if passed parameter is an array
    if (Array.isArray(elementsArray)) {
        // Start the iteration from 2nd element
        for(let i = 1; i < elementsArray.length;) {
            // Check the current element with previous element, if it is deuplicate
            if (elementsArray[i - 1] == elementsArray[i]) {
                // If found duplicate, remove the current element
                // And keep the iteration on current index only
                elementsArray.splice(i, 1);
            } else {
                i++;
            }
        }

        return elementsArray;
    } else {
        // Corner case - If passed parameter is not array, return empty array
        return [];
    }
}

const input = [1, 1, 1, 2, 3, 3, 4, 5, 6, 7, 9, 9, 9, 9];
const output = uniquElementsInArray(input);

output.forEach(i => {console.log(i + ' ')});
# In Python we are directly creating array, appending unique
# Elements and returning
def get_unique_numbers(numbers):

    # Create empty list of unique numbers
    list_of_unique_numbers = []

    # Assume at least the first data is unique
    list_of_unique_numbers.append(numbers[0])

    # Start iteration from the 2nd element, as the first element is already unique
    for i in range(1, len(numbers)):
        # Check if current element is duplicate to previous one
        if numbers[i] != numbers[i - 1]:
            list_of_unique_numbers.append(numbers[i])

    return list_of_unique_numbers


if __name__ == '__main__':
    numbers = [1, 2, 2, 3, 3, 4, 5, 5, 5]
    print(get_unique_numbers(numbers))
# result: [1, 2, 3, 4, 5]
#include<iostream>
using namespace std;

int removeDuplicates(int arr[], int n)
{
	if (n==0 || n==1)
		return 0;

	// To store index of next unique element
	// Initialize with 1, assuming at least 1 element is unique in array
	int j = 1;

	// Doing same as done in Method 1
	// Just maintaining another updated index i.e. j
	// Start the iteration from 2nd element, as the first element is unique
	for (int i=1; i < n; i++)
		if (arr[i] != arr[i - 1])
			arr[j++] = arr[i];	

    // Return new size of arr with unique element
	return j;
}

int main()
{
	int arr[9] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
	int n = sizeof(arr) / sizeof(arr[0]);

	// removeDuplicates() returns new size of array.
	int uniqueArraySize = removeDuplicates(arr, n);

	for (int i=0; i<uniqueArraySize; i++)
		cout << arr[i] << " ";

	return 0;
}
import "fmt"

func removeDuplicates(arr []int, n int) int {
	if n == 0 || n == 1 {
		return 0
	}

	// To store index of next unique element
	// Initialize with 1, assuming at least 1 element is unique in array
	var j int = 1

	// Doing same as done in Method 1
	// Just maintaining another updated index i.e. j
	// Start the iteration from 2nd element, as the first element is unique
	for i := 1; i < n; i++ {
		if arr[i] != arr[i-1] {
			arr[j] = arr[i]
			j++
		}
	}

	// Return new size of arr with unique element
	return j
}

func main() {
	inputArray := []int{1, 1, 1, 2, 3, 4, 5, 5, 5}
	var uniqueElementsIndex int = removeDuplicates(inputArray, 9)

	for i := 0; i < uniqueElementsIndex; i++ {
		fmt.Print(inputArray[i], " ")
	}
}

Leave a reply

Your email address will not be published. Required fields are marked *