# Sum of indexes of the nearest larger neighbours of each array element [closed]

Given an array A with N number of elements, for each element $i$ ($1 \le i \le N$), find $x + y$, where $x$ is the largest number less than $i$ such that $A[x] > A[i]$ and $y$ is the smallest number greater than $i$ such that $A[y] > A[i]$.

If there is no $x < i$ where $A[x] > A[i]$, $x=-1$, similarly

If there is no $y > i$ where $A[y] > A[i]$, $y=-1$

The tricky part is:

$1 \le N \le 10^6$

$1 \le A[i] \le 10^{18}$

Sample

Input:

5

5 4 1 3 2


Output:

-2 0 6 1 3


This is failing a few test cases:

#include <iostream>
using namespace std;
int main()
{
int n,i;
cin >> n;
long int a[n];
for(i=1;i<=n;i++)
cin >> a[i];
int x,y,c,d,s1,s2;
for(i=1;i<=n;i++){
c=0;
d=0;
s1=-1;
s2=-1;
x=i-1;
while(x>0){
if(a[x]>a[i]){
s1=x;
break;
}
else{
x--;
}
}
y=i+1;
while(y<=n){
if(a[y]>a[i]){
s2=y;
break;
}
else
y++;
}
int s=s1+s2;
cout << s << " ";
}
return 0;
}


## closed as off-topic by alecxe, t3chb0t, Graipher, forsvarir, HeslacherJun 29 '17 at 6:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – alecxe, t3chb0t, Graipher, Heslacher
If this question can be reworded to fit the rules in the help center, please edit the question.

• It looks to me that your code has a bug. 0 is a valid index but your while loop exits when x == 0. It should probably be set for x>=0. – tinstaafl Jun 28 '17 at 15:51
• You say it's "failing a few test cases". Is it functionally incorrect, or is it merely insufficiently performant? That's the difference between unready and ready for review. – Toby Speight Jun 28 '17 at 16:05
• Two comments either way: VLAs are not a C++ thing, and using namespace std is bad mojo. – Deduplicator Jun 28 '17 at 16:14

The code is almost unreadable. The single-letter variable names don't convey very much, the indentation is inconsistent, and the logic is opaque.

I'd start by dropping using namespace std; and separating the I/O from the program logic so that you can at least code a few test cases to ease debugging and improvement.

That variable-sized array looks risky, even with compilers that support that (non-standard) extension. Even with moderate limit of n < 1 million, that's still quite a lot to put on your stack. Consider allocating with new[] or (better) using a std::vector.

And what are c and d for? They are both set to zero, but never used.

Further points:

long int may have a size of just 32 bits at a minimum, meaning a maximum range of up to 2,147,483,647. To guarantee you can hold positive integers up to 1e18, you'll want an unsigned long long, or (better) std::uint_least64_t. Similarly, the range of int may be only -32,767 to 32,767, so I'd suggest std::uint_least32_t for the index values.

Here's how I would restructure the program:

#include <cstdint>
#include <istream>
#include <vector>

using Integer = std::uint_least64_t;
using IndexSum = std::int_least32_t;

#include <iostream>
#if TEST
int main()
{
5, 4, 1, 3, 2
});
std::vector<IndexSum>expected = {-2, 0, 6, 1, 3 };
if (actual == expected)
return 0;

for (const auto& a: {actual, expected}) {
for (auto n: a)
std::cerr << n << " ";
std::cerr << std::endl;
}

return 1;
}
#else
int main()
{
for (auto n: b)
std::cout << n << " ";
}
#endif


You can then compile with TEST defined, and refine add_closest_indices_of_greater_values() until you get the correct output:

std::vector<IndexSum> add_closest_indices_of_greater_values(const std::vector<Integer>& a)
{
std::vector<IndexSum> out;
auto n = a.size();
out.reserve(n);
for(auto i=0u;  i<n;  i++){
IndexSum s1 = -1;
IndexSum s2 = -1;
// search for nearest prior element greater than this one
for (auto x = i;  0 < x;  --x) {
if (a[x-1] > a[i]) {
s1 = x;
break;
}
}
// search for nearest following element greater than this one
for (auto x = i+1;  x < n;  ++x) {
if (a[x] > a[i]) {
s2 = x+1;
break;
}
}
out.push_back(s1+s2);
}
return out;
}


And it's a simple matter to read the input:

std::vector<Integer> read_input(std::istream& in)
{
std::vector<Integer> a;
in.exceptions(std::istream::failbit);

std::size_t n;
in >> n;
a.reserve(n);
for (size_t i = 0u;  i < n;  ++i)
in >> a[i];

return a;
}


All you need to do now is to improve the algorithm so it no longer performs a linear search for each element. You may want to instrument how many times you dereference the array, in order to reduce the complexity of the algorithm.

To begin with, valid indices to a[n] are 0 .. n-1. The loop for(i=1;i<=n;i++) accesses memory beyond the array, which invokes undefined behaviour.

The algorithm has a quadratic time complexity. There is a linearithmic solution (since it seems to be a competitive programming question, I will not spell the algorithm out).