CODEWITHSUNDEEP
c#loopsc#-4.0optimizationcomparison
Naphstor
Naphstor

Reputation: 2496

Find smallest number in given range in an array

Hi i have an array of size N. The array values will always have either 1, 2, 3 integer values only. Now i need to find the lowest number between a given range of array indices. So for e.g. array = 2 1 3 1 2 3 1 3 3 2. the lowest value for ranges like [2-4] = 1, [4-5] = 2, [7-8] = 3, etc.

Below is my code : 

static void Main(String[] args) {
    string[] width_temp = Console.ReadLine().Split(' ');
    int[] width = Array.ConvertAll(width_temp,Int32.Parse);  // Main Array              
    string[] tokens_i = Console.ReadLine().Split(' ');
    int i = Convert.ToInt32(tokens_i[0]);
    int j = Convert.ToInt32(tokens_i[1]);
    int vehicle = width[i];
    for (int beg = i+1; beg <= j; beg++) {
        if (vehicle > width[beg]) {
            vehicle = width[beg];
        }
    }
    Console.WriteLine("{0}", vehicle);
}

The above code works fine. But my concern is about efficiency. In above I am just taking one set of array range, but in actual there will be n number of ranges and I would have to return the lowest for each range. Now the problem is if there is a range like [0-N], N is array size, then I would end up comparing all the items for lowest. So I was wondering if there is a way around to optimize the code for efficiency???

Upvotes: 0

Views: 3411

Answers (4)

shole
shole

Reputation: 4094

I think it is a RMQ (Range Minimum Query) and there is several implementation which may fit your scenario.

Here is a nice TopCoder Tutorial cover a lot of them, I recommend two of them:

Using the notation in the tutorial, define <P, T> as <Preprocess Complexity, Query Complexity>, there is two famous and common implementation / data structure which can handle RMQ: Square Rooting Array & Segment Tree.

Segment Tree is famous yet hard to implement, it can solve RMQ in <O(n), O(lg n)> though, which has better complexity than Square Rooting Array (<O(n), O(sqrt(n))>)

Square Rooting Array (<O(n), O(sqrt(n))>)

Note That It is not a official name of the technique nor any data structure, indeed I do not know if there is any official naming of this technique since I learnt it...but here we go

Image from TopCoder Tutorial

For query time, it is definitely not the best you can got to solve RMQ, but it has an advantage: Easy Implementation! (Compared to Segment Tree...)

Here is the high level concept of how it works:

Let N be the length of the array, we split the array into sqrt(N) groups, each contain sqrt(N) elements.

Now we use O(N) time to find the minimum value of each groups, store them into another array call M

So using the above array, M[0] = min(A[0..2]), M[1] = min(A[3..5]), M[2] = min(A[6..8]), M[3] = min(A[9..9])

(The image from TopCoder Tutorial is storing the index of the minimum element)

enter image description here

Now let's see how to query:

For any range [p..q], we can always split this range into 3 parts at most.

Two parts for the left boundaries which is some left over elements that cannot be form a whole group.

One part is the elements in between, which forms some groups.

Using the same example, RMQ(2,7) can be split into 3 parts:

  1. Left Boundary (left over elements): A[2]
  2. Right Boundary (left over elements): A[6], A[7]
  3. In between elements (elements across whole group): A[3],A[4],A[5]

Notice that for those in between elements, we have already preprocessed their minimum using M, so we do not need to look at each element, we can look and compare M instead, there is at most O(sqrt(N)) of them (it is the length of M afterall)

For boundary parts, as they cannot form a whole group by definition, means there is at most O(sqrt(N)) of them (it is the length of one whole group afterall)

So combining two boundary parts, with one part of in between elements, we only need to compare O(3*sqrt(N)) = O(sqrt(N)) elements

You can refer to the tutorial for more details (even for some pseudo codes).

Upvotes: 2

sujith karivelil
sujith karivelil

Reputation: 29036

Form your looping like the following:

int[] inputArray = { 2, 1, 3, 1, 2, 3, 1, 3, 3, 2 };
int minIndex = 2;
int maxIndex = 5;
int minVal = 3;
for (int i = minIndex; i <= maxIndex; i++)
{
    if (inputArray[i] <= minVal)
        minVal = inputArray[i];
}
Console.WriteLine("Minimum value in the Given range is ={0}", minVal);

Upvotes: -1

Gary Holland
Gary Holland

Reputation: 2645

This seems a fun little problem. My first point would be that scanning a fixed array tends to be pretty fast (millions per second), so you'd need a vast amount of data to warrant a more complex solution.

The obvious first thing, is to break from the loop when you have found a 1, as you've found your lowest value then.

If you want something more advanced.

  1. Create a new array of int. Create a pre load function that populates each item of this array with the next index where it gets lower.
  2. Create a loop that uses the new array to skip.

Here is what I mean. Take the following arrays.

int[] intialArray = new int[] { 3, 3, 3, 3, 2, 2, 2, 1 };

int[] searchArray = new int[] { 4, 4, 4, 4, 7, 7, 7, 7 };

So the idea is to find the lowest between positions 0-7.

Start at initialArray[0] and get value 3.
Read searchArray[0] and get the value 4. The 4 is the next index where the number is lower. Read initialArray[4] and get the value 2.

etc.

So basically you'd need to put some effort to build the searcharray, but onces it's complete you would scan each range much faster.

Upvotes: 0

Hari Prasad
Hari Prasad

Reputation: 16956

You could do this using Linq extension methods.

    List<int> numbers = new List<int> {2, 1, 3, 1, 2, 3, 1, 3, 3, 2};

    int minindex =1, maxindex =3, minimum=-1;

    if(minindex <= maxindex && maxindex>=0  && maxindex >=0 && maxindex < numbers.Count())
    {
        minimum = Enumerable.Range(minindex, maxindex-minindex+1) // max inclusive, remove +1 if you want to exclude
            .Select(x=> numbers[x])    // Get the elements between given indices
            .Min();                    // Get the minimum among.    
    }

Check this Demo

Upvotes: 0

Related Questions