# A night out after long :)

October 28, 2011 5 Comments

So found the following question here (Antonio is awesum 🙂 ) and worked out a O(n) time solution **BUT** with O(n) space. I claim the space usage can be brought down to O(1). Anyone **game** enough to post the O(1) space version?

Problem:

Given an array A of numbers, find a pair of numbers A[i] and A[j], such that A[i] < A[j] and j-i is maximized.

O(n) time O(n) space code

#include <iostream> #include <string> #include <utility> #include <vector> using namespace std; int main() { vector<int> numbers; int n; cin >> n; numbers.resize(n); for (int i = 0, t; i < n; ++i) { cin >> t; numbers[i] = t; } vector<pair<int, int> > decr; decr.push_back(make_pair(numbers[0], 0)); for (int i = 1; i < numbers.size(); ++i) { if (numbers[i] < decr.back().first) { decr.push_back(make_pair(numbers[i], i)); } } vector<pair<int, int> > incr; incr.push_back(make_pair(numbers[n-1], n-1)); for (int i = n - 2; i >= 0; --i) { if (numbers[i] > incr.back().first) { incr.push_back(make_pair(numbers[i], i)); } } reverse(incr.begin(), incr.end()); int iter = min(incr.size(), decr.size()); int max_diff = -1, s_i = -1, s_j = -1; int i_i = 0, d_i = 0; for (; i_i < incr.size() && d_i < decr.size();) { if (incr[i_i].first > decr[d_i].first) { int tmp_diff = incr[i_i].second - decr[d_i].second; if (tmp_diff > max_diff) { max_diff = tmp_diff; s_i = decr[d_i].second; s_j = incr[i_i].second; } i_i++; } else if (incr[i_i].first < decr[d_i].first) { d_i++; } else { i_i++; d_i++; } } cout << "i: " << s_i << " j: " << s_j << endl; return 0; }

Advertisements

Hey avi, Here is O(1) solution.

Set current element to the starting element.

Start iterating the array from beginning and store the index of element which is smaller than current element.Update current.

Now set current2 as the ending element.

Start traversing the array from the end and store the index of element which is larger than current2.Update current2.

Now we have two indexes say i and j.

Check if i<j. If i is not less than j then such case does not occur.

Now compare a[i] with a[j]

if a[i]<a[j]

——update max to (j-i)

——update i to an index whose element is bigger than a[i] and move backwards

else

——update j to an index whose element is bigger than a[j] and move forwards

Same logic as above just optimizing space.

Two traversals.

Hi,

First, please check what is O(1) in your algorithms book.

Second, please post a working code if you have an opinion, English is too ambiguous for me. 🙂

I meant O(1) space solution.

I think you misunderstood as O(1) time solution.

@blunderboy : your algo fails to this case

5, 8, 1, 2, 3, 4

current = 2 and current2 = 1, hence current > current2 so your algo returns that case does not exist but it exist for ( 1, 4 ) which is j-i = 3 .

Hey, avi their exist a case when your given logic fails what about if first and last term are same and maximum, so in this case when you make the increasing series from back there will only be one element in it and if it matches the first way we are out of the loop and we get no solution in that case.

Eg:

This is simple case of 8 elements ( here we get correct solution)

8

11 2 3 5 0 7 3 4

i: 1 j: 7

Now what if we change the last digit from 4 to 11, then output by the algo given by you is:

8

11 2 3 5 0 7 3 11

i: -1 j: -1

which you can see is wrong, as their exist a case for i = 1, j = 6 which is solution so make changes in algo accordingly, as i might suggest to merge the case of line no 44 to 49 as

else if (incr[i_i].first <= decr[d_i].first) {

d_i++;

}