CODEWITHSUNDEEP
c++arraysalgorithm
John Roberts
John Roberts

Reputation: 5966

Beginning and Ending Array Index Algorithm

Given an unsorted array such as 9 4 4 9 2 2, I need an efficient algorithm that will allow me to know the starting location and ending location of each digit in that array, when that array is sorted. For example, for the array above, the digit 2 will have a starting index of 0 and an ending index of 1. The digit 4 will have a starting index of 2 and an ending index of 3, and the digit 9 will have a starting index of 4 and an ending index of 5 (when sorted). Anyone know how to do this in an efficient way? Is there a way to do it without sorting the array first?

Upvotes: 0

Views: 144

Answers (1)

NPE
NPE

Reputation: 500337

You can make use of the fact that there are only ten distinct elements.

First, iterate over the array once, counting the zeroes, the ones, the twos, etc.

From these counts you can easily work out the starting and the ending position of each digit in the sorted array.

This is a variant of Counting Sort, except that we don't actually populate the sorted array.

Upvotes: 5

Related Questions