A night out after long :)

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

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

5 Responses to A night out after long :)

  1. blunderboy says:

    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.

  2. Decoder says:

    @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 .

  3. rishabhaga says:

    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++;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: