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