Given integers n, l and r, generate a bitonic sequence of length n using integers from the range [l, r]. A bitonic sequence first strictly increases and then strictly decreases. There can be multiple possible sequences of the given length, you need to generate lexicographically largest sequence of al. If it is not possible to construct such a sequence, return [-1].
Note: n > 2.
Examples:
Input: n = 5, l = 3, r = 10
Output: 9, 10, 9, 8, 7
Explanation: The sequence {9, 10, 9, 8, 7} is first strictly increasing and then strictly decreasing. The other possible answers can be [7, 8, 9, 10, 9] or [8, 9, 10, 9, 8], but we need to choose the lexicographically largest one.Input: n = 7, l = 2, r = 5
Output: 2, 3, 4, 5, 4, 3, 2
Explanation: The sequence {2, 3, 4, 5, 4, 3, 2} is first strictly increasing and then strictly decreasing.
Table of Content
Using Deque - O(n) Time and O(n) Space
The idea is to first insert r - 1, then place the maximum value r as the peak of the sequence. After that, add numbers from the range [l, r] in such a way that the sequence first increases and then decreases. A deque is used so that elements can be easily inserted at both the front and back while building the bitonic sequence.
Step by step approach:
- Check if n > (r - l) * 2 + 1; if true, return [-1].
- Initialize a deque and insert r - 1.
- While the deque size is less than n, add decreasing elements from r to l at the tail.
- If needed, add increasing elements from r - 2 to l at the head.
- Convert the deque to an array and return the result.
//Driver Code Starts
using namespace std;
// Function to construct bitonic sequence of
// length n from integers in the range [l, r]
//Driver Code Ends
vector<int> bitonicArray(int n, int l, int r) {
// If not possible
if (n > (r - l) * 2 + 1) {
return {-1};
}
deque<int> dq;
dq.push_back(r-1);
// Add decreasing part
for (int i = r; i >= l && dq.size()<n; i--) {
dq.push_back(i);
}
// Add increasing part
for (int i = r - 2; i >= l && dq.size()<n; i--) {
dq.push_front(i);
}
vector<int> res(dq.begin(), dq.end());
return res;
}
//Driver Code Starts
int main() {
int n = 5, l = 3, r = 10;
vector<int> res = bitonicArray(n, l ,r);
for (auto val: res) cout << val << " ";
cout << endl;
return 0;
}
//Driver Code Ends
//Driver Code Starts
import java.util.ArrayDeque;
import java.util.Deque;
class GfG {
// Function to construct bitonic sequence of
// length n from integers in the range [l, r]
//Driver Code Ends
static int[] bitonicArray(int n, int l, int r) {
// If not possible
if (n > (r - l) * 2 + 1) {
return new int[]{-1};
}
Deque<Integer> dq = new ArrayDeque<>();
dq.addLast(r-1);
// Add decreasing part
for (int i = r; i >= l && dq.size() < n; i--) {
dq.addLast(i);
}
// Add increasing part
for (int i = r - 2; i >= l && dq.size() < n; i--) {
dq.addFirst(i);
}
int[] res = new int[dq.size()];
int idx = 0;
for (int num : dq) {
res[idx++] = num;
}
return res;
}
//Driver Code Starts
public static void main(String[] args) {
int n = 5, l = 3, r = 10;
int[] res = bitonicArray(n, l, r);
for (int val : res) {
System.out.print(val + " ");
}
System.out.println();
}
}
//Driver Code Ends
#Driver Code Starts
from collections import deque
# Function to construct bitonic sequence of
# length n from integers in the range [l, r]
#Driver Code Ends
def bitonicArray(n, l, r):
# If not possible
if n > (r - l) * 2 + 1:
return [-1]
dq = deque()
dq.append(r-1)
# Add decreasing part
i = r
while i >= l and len(dq) < n:
dq.append(i)
i -= 1
# Add increasing part
i = r - 2
while i >= l and len(dq) < n:
dq.appendleft(i)
i -= 1
return list(dq)
#Driver Code Starts
if __name__ == "__main__":
n = 5
l = 3
r = 10
res = bitonicArray(n, l, r)
print(' '.join(map(str, res)))
#Driver Code Ends
//Driver Code Starts
using System;
using System.Collections.Generic;
class GfG {
// Function to construct bitonic sequence of
// length n from integers in the range [l, r]
//Driver Code Ends
static int[] bitonicArray(int n, int l, int r) {
// If not possible
if (n > (r - l) * 2 + 1) {
return new int[]{-1};
}
LinkedList<int> dq = new LinkedList<int>();
dq.AddLast(r-1);
// Add decreasing part
for (int i = r; i >= l && dq.Count < n; i--) {
dq.AddLast(i);
}
// Add increasing part
for (int i = r - 2; i >= l && dq.Count < n; i--) {
dq.AddFirst(i);
}
int[] res = new int[dq.Count];
dq.CopyTo(res, 0);
return res;
}
//Driver Code Starts
static void Main() {
int n = 5, l = 3, r = 10;
int[] res = bitonicArray(n, l, r);
foreach (int val in res) {
Console.Write(val + " ");
}
Console.WriteLine();
}
}
//Driver Code Ends
//Driver Code Starts
// Function to construct bitonic sequence of
// length n from integers in the range [l, r]
//Driver Code Ends
function bitonicArray(n, l, r) {
// If not possible
if (n > (r - l) * 2 + 1) {
return [-1];
}
let dq = [];
dq.push(r-1);
// Add decreasing part
for (let i = r; i >= l && dq.length < n; i--) {
dq.push(i);
}
// Add increasing part
for (let i = r - 2; i >= l && dq.length < n; i--) {
dq.unshift(i);
}
return dq;
}
//Driver Code Starts
let n = 5, l = 3, r = 10;
let res = bitonicArray(n, l, r);
console.log(res.join(' '));
//Driver Code Ends
Output
9 10 9 8 7
Using Pre-calculation - O(n) Time and O(n) Space
The idea is to pre calculate how many numbers need to be added to the increasing and decreasing parts of the sequence, then build the sequence directly by placing the maximum value first, followed by carefully chosen values to fulfill the bitonic property.
//Driver Code Starts
using namespace std;
// Function to construct bitonic sequence of
// length n from integers in the range [l, r]
//Driver Code Ends
vector<int> bitonicArray(int n, int l, int r) {
// If not possible
if (n > (r - l) * 2 + 1) {
return {-1};
}
// Count of decreasing values, starting from r
int decreasingCount = min(n-1, r-l+1);
int increasingCount = n - 1 - decreasingCount;
vector<int> res;
// Insert increasing values.
while (increasingCount > 0) {
res.push_back(r - 1 - increasingCount);
increasingCount--;
}
// Maximum value before peak.
res.push_back(r - 1);
// Insert decreasing values.
for (int i=r; i>=l && decreasingCount>0; i--) {
res.push_back(i);
decreasingCount--;
}
return res;
}
//Driver Code Starts
int main() {
int n = 5, l = 3, r = 10;
vector<int> res = bitonicArray(n, l ,r);
for (auto val: res) cout << val << " ";
cout << endl;
return 0;
}
//Driver Code Ends
//Driver Code Starts
import java.util.ArrayList;
class GfG {
// Function to construct bitonic sequence of
// length n from integers in the range [l, r]
//Driver Code Ends
static int[] bitonicArray(int n, int l, int r) {
// If not possible
if (n > (r - l) * 2 + 1) {
return new int[]{-1};
}
// Count of decreasing values, starting from r
int decreasingCount = Math.min(n-1, r-l+1);
int increasingCount = n - 1 - decreasingCount;
ArrayList<Integer> resList = new ArrayList<>();
// Insert increasing values.
while (increasingCount > 0) {
resList.add(r - 1 - increasingCount);
increasingCount--;
}
// Maximum value before peak.
resList.add(r - 1);
// Insert decreasing values.
for (int i=r; i>=l && decreasingCount>0; i--) {
resList.add(i);
decreasingCount--;
}
// Convert ArrayList to array
int[] res = new int[resList.size()];
for (int i=0; i<resList.size(); i++) {
res[i] = resList.get(i);
}
return res;
}
//Driver Code Starts
public static void main(String[] args) {
int n = 5, l = 3, r = 10;
int[] res = bitonicArray(n, l, r);
for (int val : res) {
System.out.print(val + " ");
}
System.out.println();
}
}
//Driver Code Ends
#Driver Code Starts
# Function to construct bitonic sequence of
# length n from integers in the range [l, r]
#Driver Code Ends
def bitonicArray(n, l, r):
# If not possible
if n > (r - l) * 2 + 1:
return [-1]
# Count of decreasing values, starting from r
decreasingCount = min(n-1, r-l+1)
increasingCount = n - 1 - decreasingCount
res = []
# Insert increasing values.
while increasingCount > 0:
res.append(r - 1 - increasingCount)
increasingCount -= 1
# Maximum value before peak.
res.append(r - 1)
# Insert decreasing values.
i = r
while i >= l and decreasingCount > 0:
res.append(i)
i -= 1
decreasingCount -= 1
return res
#Driver Code Starts
if __name__ == "__main__":
n = 5
l = 3
r = 10
res = bitonicArray(n, l, r)
print(' '.join(map(str, res)))
#Driver Code Ends
//Driver Code Starts
using System;
using System.Collections.Generic;
class GfG {
// Function to construct bitonic sequence of
// length n from integers in the range [l, r]
//Driver Code Ends
static int[] bitonicArray(int n, int l, int r) {
// If not possible
if (n > (r - l) * 2 + 1) {
return new int[]{-1};
}
// Count of decreasing values, starting from r
int decreasingCount = Math.Min(n-1, r-l+1);
int increasingCount = n - 1 - decreasingCount;
List<int> resList = new List<int>();
// Insert increasing values.
while (increasingCount > 0) {
resList.Add(r - 1 - increasingCount);
increasingCount--;
}
// Maximum value before peak.
resList.Add(r - 1);
// Insert decreasing values.
for (int i=r; i>=l && decreasingCount>0; i--) {
resList.Add(i);
decreasingCount--;
}
return resList.ToArray();
}
//Driver Code Starts
static void Main() {
int n = 5, l = 3, r = 10;
int[] res = bitonicArray(n, l, r);
foreach (int val in res) {
Console.Write(val + " ");
}
Console.WriteLine();
}
}
//Driver Code Ends
//Driver Code Starts
// Function to construct bitonic sequence of
// length n from integers in the range [l, r]
//Driver Code Ends
function bitonicArray(n, l, r) {
// If not possible
if (n > (r - l) * 2 + 1) {
return [-1];
}
// Count of decreasing values, starting from r
let decreasingCount = Math.min(n-1, r-l+1);
let increasingCount = n - 1 - decreasingCount;
let res = [];
// Insert increasing values.
while (increasingCount > 0) {
res.push(r - 1 - increasingCount);
increasingCount--;
}
// Maximum value before peak.
res.push(r - 1);
// Insert decreasing values.
for (let i=r; i>=l && decreasingCount>0; i--) {
res.push(i);
decreasingCount--;
}
return res;
}
//Driver Code Starts
let n = 5, l = 3, r = 10;
let res = bitonicArray(n, l, r);
console.log(res.join(' '));
//Driver Code Ends
Output
9 10 9 8 7