# almostIncreasingSequence

This is assignment from codesignal:

Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

fn almostIncreasingSequence(sequence: Vec<i32>) -> bool {
if sequence.len() == 2
|| sequence.len() == 3 && (sequence[1] > sequence[0] || sequence[2] > sequence[1])
{
true
} else {
let mut no_increase = sequence[1] <= sequence[0];
for i in 2..(sequence.len() - 1) {
//println!("sequence[{}] {}", i, sequence[i]);
//println!("no_increase {:?}", no_increase);
if sequence[i] <= sequence[i - 1] {
if no_increase
|| sequence[i] <= sequence[i - 2] && sequence[i + 1] <= sequence[i - 1]
|| i == (sequence.len() - 2) && sequence[i + 1] <= sequence[i]
{
return false;
}
no_increase = true;
} else if i == (sequence.len() - 2) && no_increase && sequence[i + 1] <= sequence[i] {
return false;
}
}
true
}
}

#[test]
fn test_almostIncreasingSequence() {
let samples: Vec<(Vec<i32>, bool)> = vec![
(vec![3, 6, -2, -5, 7, 3], false),
(vec![1, 3, 2, 1], false),
(vec![1, 2, 1, 2], false),
(vec![0, -2, 5, 6], true),
(vec![10, 1, 2, 3, 4, 5], true),
(vec![40, 50, 60, 10, 20, 30], false),
(vec![3, 6, 5, 8, 10, 20, 15], false),
(vec![1, 1, 2, 3, 4, 4], false),
];

for (inputArray, expected) in samples {
println!("\n{:?}", inputArray);
assert_eq!(expected, almostIncreasingSequence(inputArray));
}
}


Run with cargo test test_almostIncreasingSequence

Edit: Added check for i == (sequence.len() - 2) element

Edit: Added more tests as suggested which showed bug for sequence.len() == 3. Now fixed:

fn almostIncreasingSequence(sequence: Vec<i32>) -> bool {
if sequence.len() < 3 {
true
} else if sequence.len() == 3 {
sequence[1] > sequence[0] || sequence[2] > sequence[1] || sequence[2] > sequence[0]
} else {
let mut no_increase = sequence[1] <= sequence[0];
for i in 2..(sequence.len() - 1) {
//println!("sequence[{}] {}", i, sequence[i]);
//println!("no_increase {:?}", no_increase);
if sequence[i] <= sequence[i - 1] {
if no_increase
|| sequence[i] <= sequence[i - 2] && sequence[i + 1] <= sequence[i - 1]
|| i == (sequence.len() - 2) && sequence[i + 1] <= sequence[i]
{
return false;
}
no_increase = true;
} else if i == (sequence.len() - 2) && no_increase && sequence[i + 1] <= sequence[i] {
return false;
}
}
true
}
}

#[test]
fn test_almostIncreasingSequence() {
let samples: Vec<(Vec<i32>, bool)> = vec![
(vec![], true),
(vec![1], true),
(vec![1, 1], true),
(vec![1, 1, 1], false),
(vec![3, 6, -2, -5, 7, 3], false),
(vec![1, 3, 2, 1], false),
(vec![1, 2, 1, 2], false),
(vec![0, -2, 5, 6], true),
(vec![10, 1, 2, 3, 4, 5], true),
(vec![40, 50, 60, 10, 20, 30], false),
(vec![3, 6, 5, 8, 10, 20, 15], false),
(vec![1, 1, 2, 3, 4, 4], false),
];

for (inputArray, expected) in samples {
println!("\n{:?}", inputArray);
assert_eq!(expected, almostIncreasingSequence(inputArray));
}
}


Edit: Checking for edge case moved out of loop.

fn almostIncreasingSequence(sequence: Vec<i32>) -> bool {
if sequence.len() < 3 {
true
} else if sequence.len() == 3 {
sequence[1] > sequence[0] || sequence[2] > sequence[1] || sequence[2] > sequence[0]
} else {
let mut no_increase = sequence[1] <= sequence[0];
for i in 2..(sequence.len() - 1) {
//println!("sequence[{}] {}", i, sequence[i]);
//println!("no_increase {:?}", no_increase);
if sequence[i] <= sequence[i - 1] {
if no_increase
|| sequence[i] <= sequence[i - 2] && sequence[i + 1] <= sequence[i - 1]
{
return false;
}
no_increase = true;
}
}

if no_increase && sequence[sequence.len() - 1] <= sequence[sequence.len() - 2] {
return false;
}
true
}
}

• Almost increasing? I'd say it's either increasing or it isn't, but I suspect the actual problem assignment would clarify this. Can you post more about what the code is supposed to do? The line "We can remove only one element in the process." isn't clear either.
– Mast
Commented Jan 16, 2020 at 14:17
• I have added original description Commented Jan 16, 2020 at 14:31
• I recommend adding test cases for sequences of length 0, 1, 2, and 3. The first two are common special cases for problems like these, and the latter two are special cased in your implementation. Commented Feb 9, 2020 at 19:43
• @cbojar Thanks. With that I found a bug. Commented Feb 10, 2020 at 13:17