How to find the maximum number possible in an array given constraints?

Question

I'm working on a problem where I need to construct an array of size N such that the array adheres to the following constraints:

The first element of the array is always 0 (arr[0] = 0). The difference between adjacent elements is less than or equal to 1 (|arr[i] - arr[i-1]| <= 1). We are given M pairs (x, y), which specify that the value at index x cannot exceed y (arr[x] <= y). All the values of array must be positive integers Given these constraints, I need to determine the maximum possible value in the array.

Here are some example test cases:

N = 5, M = 4 with pairs (1, 0), (2, 0), (3, 0), (4, 0) Possible array: [0, 0, 0, 0, 0] Answer: 0

N = 5, M = 1 with pair (3, 0) Possible array: [0, 1, 1, 0, 1] Answer: 1

N = 10, M = 1 with pair (3, 1) Possible array: `[0, 1, 2, 1,2,3,4,5,6] answer is 6

fourth test case N = 10, M =2 (1,1) (3,4)

array : [0,1,2,3,4] answer is 4

I tried but failed on some test cases

example: N = 10, M = 3 (3,20) (7,50) (9,1)

"I'm working on a problem...": please show your work, and explain what is holding you back to achieve what you described. — trincot
– trincot, Commented Jun 18, 2024 at 7:11
@trincot I am unable to figure out solution that works for all test cases. — sarvesh kumar
– sarvesh kumar, Commented Jun 18, 2024 at 9:07
I understand that, but please show your work so we can tell you where you went wrong. — trincot
– trincot, Commented Jun 18, 2024 at 9:53

Gassa · Accepted Answer · 2024-06-18 09:57:57Z

This is a bit short of a full answer, but a strong hint nonetheless.

For simplicity, let us first consider a version with constraints at every integer point from 0 to N, inclusive.

So, we have the following problem:

arr[0]   <= 0
arr[1]   <= v[1]
arr[2]   <= v[2]
...
arr[N-1] <= v[N-1]
arr[N]   <= infinity

We add arr[0] <= 0 for completeness, and arr[N] <= infinity if there is no other constraint at x = N.

Now, consider the conditions at every point:

arr[x]   <= arr[x-1] + 1
arr[x]   <= arr[x+1] + 1

Turns out these can be satisfied with just two passes over the array.

The first pass will be from left to right, and we will satisfy the former constraint. When we came to point x, all left-side constraints from 1 to x-1 are already incorporated into the single value of arr[x-1].

for i = 1, 2, ..., N:
    arr[i] := min (arr[i], arr[i - 1] + 1)

The second pass will be from right to left, and we will satisfy the latter constraint. When we came to point x, all right-side constraints from x+1 to N are already incorporated into the single value of arr[x+1].

for i = N, N-1, ..., 1:
    arr[i] := min (arr[i], arr[i + 1] + 1)

To find the maximum, just iterate over the array.

The original problem features constraints only at certain points. And perhaps the solution should take linear time in the number of points.

So, instead of considering all integer points, we will write analogous left-side and right-side conditions, but featuring the previous and the next given points. We should add zero at x=0 and infinity at x=N for completeness. Two passes will again be sufficient.

To find the maximum, first, iterate over the array. Additionally, consider the highest possible point on each segment between two consecutive given points: each such segment is a subproblem solvable in constant time.

Collectives™ on Stack Overflow

How to find the maximum number possible in an array given constraints?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related