5
\$\begingroup\$

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
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Mast Jan 16 at 14:17
  • 1
    \$\begingroup\$ I have added original description \$\endgroup\$ – rofrol Jan 16 at 14:31
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – cbojar Feb 9 at 19:43
  • \$\begingroup\$ @cbojar Thanks. With that I found a bug. \$\endgroup\$ – rofrol Feb 10 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.