CODEWITHSUNDEEP
arraysalgorithmstacktime-complexity
rotemhas
rotemhas

Reputation: 81

The longest sub-array that all the elements less or equal A[i]

I have an array A[1,...,n] of positive numbers, for example:

[1, 2, 5, 3, 7, 2, 8, 4]

I need to build an array S[1,...,n] according to the definition:

S[i] = max {k|∀i−k <j≤i :A[j] ≤ A[i] and k ≤ i}

It means to find the longest sub-array A[i − k,..,i] that all of its elements are less or equal A[i] for each index in the array.

I need to write an algorithm that creates the array S in O(n) using Stack.

For example for the array [1,2,4,3,5] i need to return the array [1,2,3,2,5]

Thank you.

Upvotes: 0

Views: 251

Answers (1)

MAnyKey
MAnyKey

Reputation: 567

You can store (current_maximum, size_of_sequence) in stack for each sequence of increasing numbers. On each iteration you should add value to sequence (optionally merging adjacent sequences if new value is bigger)

#include <stack>
#include <vector>
#include <utility>

std::vector<int> leq_subarrays(const std::vector<int>& numbers) {
  if (numbers.empty()) {
    return std::vector<int>();
  }
  std::vector<int> answer(numbers.size());
  std::stack<std::pair<int, int>> s;
  s.push(std::make_pair(numbers[0], 1));
  answer[0] = 1;
  for (size_t i = 1; i < numbers.size(); ++i) {
    const auto& value = numbers[i];
    int count = 1;
    while (!s.empty() && s.top().first <= value) {
      count += s.top().second;
      s.pop();
    }
    s.push(std::make_pair(value, count));
    answer[i] = count;
  }
  return answer;
}

Link to Ideone: http://ideone.com/SlZorX

Upvotes: 1

Related Questions