2
\$\begingroup\$

The question

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.

My java solution

boolean almostIncreasingSequence(int[] sequence) {

    Integer[] arr = new Integer[sequence.length];

    for(int ctr = 0; ctr < sequence.length; ctr++) {
        arr[ctr] = Integer.valueOf(sequence[ctr]); // returns Integer value
    }
    System.out.println("Integer :: " + arr);
    List<Integer> al = new ArrayList<Integer>(); 

    // adding elements of array to arrayList. 
    Collections.addAll(al, arr);
    System.out.println("list :: " + al);
    int save, flag = 0;
    for(int i=0; i<al.size(); i++) {
        save = al.get(i);
        al.remove(i);
        if(al.size()==1) return true;
        for(int j=0; j<al.size()-1; j++) {
            if(al.get(j+1) > al.get(j)) {
                flag = 0;
                continue;
            }
            else {
                flag = 1;
                break;
            }
        }
        if(flag == 0) {
            return true;
        }
        al.add(i,save);
    }

    if(flag == 1)
        return false;
    return true;
}

Here, I have created 2 for loops because in the first loop I'm generating the list where each index will be removed and in the second loop I'm iterating over the new list which has removed the element.

like sample array is {1,2,4,3} then in the first loop I'm creating an array which will be {2,4,3},{1,4,3},{1,2,3} and {1,2,4}. In the second loop I'm iterating over all these 4 arrays to compare each element.

The problem

For some of the test cases, it shows that it takes more than 3 seconds to execute this. But, I'm not sure where can I make a change to execute it faster. I don't have access to the test case.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly. \$\endgroup\$
    – Martin R
    Jan 23 '19 at 7:45
  • \$\begingroup\$ Hi Virus and welcome to codereview! I took the liberty to change the title and restructure your question to make it clearer. If you think I changed it too much feel free to edit it again. \$\endgroup\$
    – Imus
    Jan 23 '19 at 10:55
1
\$\begingroup\$

You are repeating a lot of work.

For example, let's take a look at the sequence [1,2,3,4,5].

Your code does the following:
- copy it to a list
- remove "1" and check if {2,3,4,5} is sorted
- remove "2" and check if {1,3,4,5} is sorted
- remove "3" and check if {1,2,4,5} is sorted
- remove "4" and check if {1,2,3,5} is sorted
- remove "5" and check if {1,2,3,4} is sorted

Instead, let's go over the entire sequence once and do something special on the first item that is smaller than the previous one.

At some point into the loop we see the following where sequence[i-1] > sequence[i]

{done part, a, sequence[i-1], sequence[i], c, remainder}

The whole start of the sequence up to sequence[i-1] is strictly increasing (checked in earlier iterations of the loop). So what do we still need to check here to give a meaningful answer?

Given that sequence[i-1]>sequence[i] either one of those needs to be removed. So we have 2 cases:

  • remove sequence[i-1] -> check if {a, sequence[i], c, remainder} is strictly increasing
  • remove sequence[i] -> check if {a, sequence[i-1], c, remainder} is strictly increasing

Note that in both cases we want to check if the remainder is strictly ascending. So the main loop will look something like this:

for(int i = 1; i < sequence.length; i++){
    if (sequence[i - 1] > sequence[i]) {
        // {..., a, sequence[i-1], sequence[i], c, remainder}
        //check if remainder is sorted
        for(int j = i+1; j < sequence.length; j++){
            if (sequence[j - 1] > sequence[j]) {
                return false;
            }
        }
        int a = sequence[i - 2];
        int c = sequence[i + 1];
        //remove i-1
        if (a < sequence[i] && sequence[i] < c) {
            return true;
        }
        //remove i
        if (a < sequence[i - 1] && sequence[i - 1] < c) {
            return true;
        }
        //neither removing i-1 or i fixed the strictly increasing rule
        return false;
    }
}
//entire list is strictly increasing
return true;

There's still some edge cases that will cause trouble. This loop as it is now will throw an ArrayIndexOutOfBoundsException because we're accessing from sequence[i-2] up to sequence[i+1].

Let's handle those cases before the loop to keep things as simple as possible and reduce the bounds for the loop:

//trivial case with up to 2 items
if(sequence.length < 3){
    return true;
}
//edge case first 3 items are descending
if(sequence[0]>sequence[1]
        &&sequence[1]>sequence[2]) {
    return false;
}
//edge case last 3 items are descending
int last = sequence.length-1;
if(sequence[last-2]>sequence[last-1]
        &&sequence[last-1]>sequence[last]) {
    return false;
}
for(int i = 2; i < sequence.length-1; i++){ //skip first 2 and last item
    ...

With this we're no longer checking the same items over and over again and we no longer copy all the items into a list which should give you a major improvement in speed.


DISCLAIMER I have not tested this code. It's possible it contains typo's or other edge cases. Be sure to fully understand it instead of blindly copy-pasting.

\$\endgroup\$
2
  • \$\begingroup\$ If seq[0] > seq[1] && seq[1] > seq[2], then seq[0] > seq[2] must be true, so can be removed from the first 3 items are descending test. Ditto for the last 3 items are descending test. \$\endgroup\$
    – AJNeufeld
    Jan 23 '19 at 23:15
  • \$\begingroup\$ @AJNeufeld True, editted :) \$\endgroup\$
    – Imus
    Jan 24 '19 at 8:17
0
\$\begingroup\$

I think your question only needs you to determine if there is more than one integer out of sequence in the array passed in.

You could just loop through the array passed in and if you find an integer out of sequence count it, then jump over it.

If you find a second integer out of sequence then return false, if you don't find another in the array then return true. You should be able to achieve this with one loop which will speed up your code..

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I thought so too at first but that's not enough. Take the sequence [3,4,1,2] where you only see 1 drop yet you can't fix it by taking only 1 item out. \$\endgroup\$
    – Imus
    Jan 23 '19 at 12:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.