Given an array, A[] of N integers and 2 integers P and Q, the task is to construct an array of minimum possible length with given P and Q and absolute difference of consecutive elements equal to 1such that:

• P is the sum of all the elements A[i] of the array such that A[i] > A[(i+1) % N] and A[i] > A[(i-1+N) % N].
• Q is the sum of all the elements A[i] of the array such that A[i] < A[(i+1) % N] and A[i] < A[(i-1+N) % N].

Examples:

Input: P = 3, Q = -2
Output: {0, 1, 2, 1, 0, -1, 0, -1, 0, 1}
Explanation: It can be seen that the absolute difference between all the adjacent elements is 1. Also, we can see elements at positions 3, 7 and 10 are greater than both of their neighbours. So, 
P = 2 + 0 + 1 = 3. Also, elements at positions 1, 6, and 8 are lesser than both of their neighbors. So, Q = 0 + (-1) + (-1) = -2. Note that {-1, 0, 1, 2, 3, 2, 1, 0 } is also a valid answer.

Input: P = 2, Q = -1
Output: {1, 0, -1, 0, 1, 0}

Approach: To solve the problem follow the below observations:

The problem is observation-based. Let’s look into each observation one by one:

Observation 1: The elements greater than their neighbors would alternate to the elements smaller than their neighbors. Also, they would be the same in number, say K.

Let p(i) be ith element greater than both of its neighbors and q[i] be the ith element smaller than both the neighbors. To get to q(i) from p(i), we would need p(i)-q(i) elements (as the absolute difference should be 1). So, the minimum possible total elements in the array will be  (a(1)-b(1)) + (a(2)-b(1)) + (a(2)-b(2)) +…..+(a(K)-b(K)) + (a(1)-b(K))
= 2*(a(1)+a(2)…a(K)) – 2*(b(1)+b(2)…b(K)) 
= 2*(P-Q).

Observation 2: The array [Q, Q+1, Q+2,….,P−1, P, P−1, P−2,…, Q+1] will satisfy all the conditions.

Steps that were to follow the above approach:

• Initialize an array A[] of size 2*(P-Q).
• Initialize a variable idx = 0.
• Iterate from i=Q to P. At each iteration, set A[idx] = i and increment idx simultaneously.
• Again, Iterate from i=P-1 to Q+1 in reverse. At each iteration, set A[idx] = i and increment idx simultaneously.
• Finally, print the resultant array.

Below is the code to implement the above steps:

-1 0 1 2 3 2 1 0 

Time Complexity: O(N), where N=2*(P-Q)
Auxiliary Space: O(N), where N=2*(P-Q)