A night out after long :)
October 28, 2011 4 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;
}
Advertisement
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 .