programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Devaka Cooray
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Knute Snortum
• Junilu Lacar
• paul wheaton
Saloon Keepers:
• Ganesh Patekar
• Frits Walraven
• Tim Moores
• Ron McLeod
• Carey Brown
Bartenders:
• Stephan van Hulst
• salvin francis
• Tim Holloway

# Is there any way of an infinite loop here?

Ranch Hand
Posts: 109
2
So I was on Code Fights recently and I am barely on level 2 in Java. Here is a task I have recently stumbled on.
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.

Example

For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].
The code I wrote works for all cases except for one:

The non-working case is a hidden case so I have no idea what case where I would have an infinite loop. Can you see the reason for such an error?

Marshal
Posts: 6255
420

Sergiu Dobozi wrote:The non-working case is a hidden case so I have no idea what case where I would have an infinite loop.

So, you say the problem is that on some inputs you'd run into infinite (non ending) program?

I see problem if sequence is either empty or null, so you don't check for those, but these cases wouldn't cause anything infinite. Please clarify or better copy paste exact text from where you take this challenge.

Sheriff
Posts: 12739
210
• 2
Why do you assume it's an infinite loop that's the problem? Any An array with less than three elements and non-increasingly ordered values will fail a test because it will result in your sorted() method returning true. I doubt that a zero- or one-element array should be considered as an increasing sequence. To tell if you have a strictly increasing sequence, you need at least two elements, don't you?

I think it's your sorted method that's the problem.

Junilu Lacar
Sheriff
Posts: 12739
210
Take for example the sequence [3, 1] : can you take away at most one element to get strictly increasing sequence? Assuming a strictly increasing sequence has to have at least 2 elements, then you can't, so this should return false. Your program, however, will return true.

Sergiu Dobozi
Ranch Hand
Posts: 109
2

Junilu Lacar wrote:Why do you assume it's an infinite loop that's the problem? Any array with less than three elements will probably fail a test because it will result in your sorted() method returning true. I doubt that a zero- or one-element array should be considered as an increasing sequence. To tell if you have a strictly increasing sequence, you need at least two elements, don't you?

I think it's your sorted method that's the problem.

This is what Code Fights gives me as an error:
"Execution time limit exceeded on test 26: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input."

So I assumed that it is referring to an infinite loop.

Liutauras Vilda
Marshal
Posts: 6255
420
Alright, so problem is different.

What you do, lets say on input {1, 2, 7, 4, 0, 5, 6, ... N-1}. You copy whole array and then checking if it's sorted. But you know right away after 2, 7, 4, ... 0... that this combination can't be sorted, but you still going to copy the rest of the elements.

Junilu Lacar
Sheriff
Posts: 12739
210
Probably a more difficult challenge is to come up with a recursive solution that doesn't use explicit iteration, just array slices. I know that array slices are a somewhat foreign term for most Java programmers and there's no native language support for them but you can write a utility class and use java.util.Arrays to get them.

Liutauras Vilda
Marshal
Posts: 6255
420
And i'm not sure why you need to do all that copying. You can I think just check previous element if it is smaller. Then advance counter, and again...

Liutauras Vilda
Marshal
Posts: 6255
420
Thinking a bit in a rush now, but i think you just need to find first element which is smaller than previous, then skip that and check if the rest elements are greater than the one before you skipped, and that is it I think.

 hm.. that might won't work in some cases.. don't know about that now

Junilu Lacar
Sheriff
Posts: 12739
210
• 1
Liutauras is correct about long arrays.  I tried with 50K numbers and it took a few seconds to complete on my Mac. This code will eventually fail for long arrays, depending on how impatient the test harness is.

Sergiu Dobozi
Ranch Hand
Posts: 109
2

Liutauras Vilda wrote:Thinking a bit in a rush now, but i think you just need to find first element which is smaller than previous, then skip that and check if the rest elements are greater than the one before you skipped, and that is it I think.

 hm.. that might won't work in some cases.. don't know about that now

This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.
This is my implementation:

Sergiu Dobozi
Ranch Hand
Posts: 109
2

Junilu Lacar wrote:Liutauras is correct about long arrays.  I tried with 50K numbers and it took a few seconds to complete on my Mac. This code will eventually fail for long arrays, depending on how impatient the test harness is.

Thank you for testing it. I'm at work so I don't have access to any programming software.
Now I know that at least there was no logical problem.

Master Rancher
Posts: 3001
105
Well, it is not an infinite loop, but OP'current implementation will have a solution time that is very dependent on the array in question.
As Junilu writes, if an array is already sorted, then the progrram will terminate very quickly, since the first attempt will be succesfull, However, with an average array, run time will go up dramatically. For instance try:

This will very quickly end. But when running with the outcommented line will probably get you the time exceeds error.

Another way, find the two biggest elements and write down their indices. Now, if these indices are the two highest indices (array.length - 1 and array.length - 2), then what can you conclude? And what if these indices are not the highest two indices? That will give you a O(N) solution, if I'm not mistaken (which has a positive probability...)

Edit: well, the above is not correct, but it is in the right direction...

Liutauras Vilda
Marshal
Posts: 6255
420

Sergiu Dobozi wrote:This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.

That's not true.

Let me rephrase all that from a different end, I might wasn't clear enough. Find first element which is equal greater than next, skip that element, record that you removed/skipped one already, if that happens again, return false, otherwise true.

Liutauras Vilda
Marshal
Posts: 6255
420

Piet Souris wrote:Another way, find the two biggest elements and write down their indices..And what if these indices are not the highest two indices?..That will give you a O(N) solution

So, at best it is O(N), mine described algorithm above at worst O(N).

Rancher
Posts: 3746
40

Sergiu Dobozi wrote:
This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.

But it's a start point.

There are two situations, both of which can be initially spotted using Liutauras' suggestion.

10,20,30,20,40,50
in which you want to remove the low value, which can be spotted by the fact that 30 < 40, so 20 is the odd one out.

1, 2, 3, 4, 99, 5, 6
in which you spot the issue on the '5', but because 99 > 6 then it's the 99 that goes.

That should be a pretty simple check.

So, search as per Liutauras' idea, then check either side of the first value you hit where currentValue < previousValue...if previousValue < nextValue then remove currentValue...if previousValue > nextValue, remove previousValue.

There's probably other issues, but it's a start.

Sergiu Dobozi
Ranch Hand
Posts: 109
2

Dave Tolls wrote:

Sergiu Dobozi wrote:
This doesn't work for cases like when we have an array such as {1, 2, 3, 4, 99, 5, 6} or {1000, 400, 500, 600} because it would return false rather than true.

But it's a start point.

There are two situations, both of which can be initially spotted using Liutauras' suggestion.

10,20,30,20,40,50
in which you want to remove the low value, which can be spotted by the fact that 30 < 40, so 20 is the odd one out.

1, 2, 3, 4, 99, 5, 6
in which you spot the issue on the '5', but because 99 > 6 then it's the 99 that goes.

That should be a pretty simple check.

So, search as per Liutauras' idea, then check either side of the first value you hit where currentValue < previousValue...if previousValue < nextValue then remove currentValue...if previousValue > nextValue, remove previousValue.

There's probably other issues, but it's a start.

I will have to try out everyone's suggestions as soon as possible.
If there is a case where {1000, 20, 30, 40} and I have to check 1000 with a previous value, I can't do that because I would have to compare with sequence[-1]. So is this method really possible to implement?

Junilu Lacar
Sheriff
Posts: 12739
210
I wrote a 1-pass fail-fast loop and got decent performance. I tested with an int[Integer.MAX_VALUE / 8] and (seemingly) still got sub-second time to complete.

I used ChronoUnits and LocalDateTime so I might not be doing it right but I don't see much delay on the console.

and here's my output:

0 secs 52 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 197 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass
0 secs 0 millis
Pass

I suppose the first test always takes a hit for loading and other kinds of startup overhead. The 197 millis was for the Integer.MAX_VALUE / 8 long array of sequential numbers.  Couldn't use the max because I was running out of memory for the array.

Junilu Lacar
Sheriff
Posts: 12739
210
Basically, my algorithm counted drops, i.e., when arr[i] >= arr[i+1].  If you count more than 1 drop, then there is no need to proceed further.  Of course, when you find a drop, you have to check if dropping the high number will still result in a drop from the previous element. There are a couple of special cases that I checked up front, then I went into the general case that was covered by the fail-fast loop, which is only 7 lines of executable code, 10 lines if you count the lines with closing braces.  The almostSequential() method I wrote is about 12 lines of executable code, 20 lines with whitespace and full bracing.

Junilu Lacar
Sheriff
Posts: 12739
210

Sergiu Dobozi wrote:This is my implementation:

[100, 1, 2]
**Fail**

[1, 2, 4, 100, 4]
**Fail**

[1]
**Fail**

[2, 1]
**Fail**

Dave Tolls
Rancher
Posts: 3746
40

Sergiu Dobozi wrote:
I will have to try out everyone's suggestions as soon as possible.
If there is a case where {1000, 20, 30, 40} and I have to check 1000 with a previous value, I can't do that because I would have to compare with sequence[-1]. So is this method really possible to implement?

Others may work differently, but I always suggest getting the basics down first (Junilu's tests are good for that).
Handle the edge cases once you've handled the general case.
In my opinion, trying to write something outright that covers all cases tends to result in you writing nothing.

Junilu Lacar
Sheriff
Posts: 12739
210

Dave Tolls wrote:I always suggest getting the basics down first (Junilu's tests are good for that). Handle the edge cases once you've handled the general case.

Minds that think alike...

Ironically, I missed one test case that you pointed out, Dave: [10, 20, 30, 40, 20, 50]

Sure enough, when I ran it, my implementation failed. It actually took me a while to figure out how to cover this one but with some refactoring to clarify intent, the code eventually pointed me to the right solution. I found a very good example of how too many implementation details can make it difficult to catch and eradicate a bug.    I will share my solution once we see one from OP that passes all the tests I wrote.

Saloon Keeper
Posts: 5137
54

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.

• What is meant by "strictly"? (I'm assuming I can ignore this.)
• Does each number have to be 1 more than the one before it? (assume: no)
• Does the interval between successive pairs have to be the same? (assume: no)
• Is a single number, e.g. [1], a "sequence"? (assume: no)

• Test cases that should return true

Test cases that should return false

I'm wondering if anyone disagrees with my test cases? Obviously Junilu and I disagree on one of them.

Junilu Lacar
Sheriff
Posts: 12739
210

Carey Brown wrote:

• What is meant by "strictly"? (I'm assuming I can ignore this.)
• Does each number have to be 1 more than the one before it? (assume: no)

• I think the second is what defines "strictly", that is, each number must be at least one more than the previous one, if there is one. "Non-strictly" speaking, you'd allow repeats of the same number.

• Does the interval between successive pairs have to be the same? (assume: no)
• Is a single number, e.g. [1], a "sequence"? (assume: no)

• I made the same assumptions.

[1, 2, 4, 100, 4] // I disagree w/ Junilu on this one, I'd drop the last '4'[/code]
I'm wondering if anyone disagrees with my test cases? Obviously Junilu and I disagree on one of them.

You're correct to disagree with me on this one. I do, too. That was a mistake and it's a faulty test because it has another solution than the one being tested. I actually spent literally 30 minutes refactoring my code to clarify intent before I realized this. I should have read your post earlier; I could have saved myself the frustration.

Junilu Lacar
Sheriff
Posts: 12739
210
Here's my cleaned up test harness. It would have been easier to write a JUnit test but I was on a roll so I just kept going with it...

Carey Brown
Saloon Keeper
Posts: 5137
54
• 1

Carey Brown
Saloon Keeper
Posts: 5137
54
OK Junilu, I concede. Changed my algorithm and swapped those specific true/false cases.
New output:

Carey Brown
Saloon Keeper
Posts: 5137
54
There's been an offline discussion on whether [], [1], [1,1], or [2,1] should result in a false outcome, and I guess I'm throwing my hat in with Junilu to say that these are false, meaning that after potentially dropping an element the results no longer represent a "sequence".

Here's the test cases that have come up so far:

The results for the OP's algorithm:

Liutauras Vilda
Marshal
Posts: 6255
420
Junilu, thanks for great tests. Carey, thanks for reporting your progress - it made me look further to this. Have both cows. Cow for OP too for giving us chance to have fun.

I've fixed my algorithm as per failing cases. Since the beginning problem looked very simple, to come up with a starting algorithm took me around 10 minutes, oh well, I guess simple problem is simple as long as you have all possible different scenarios covered within tests.
On friday I wrote for myself around 15 test cases, but haven't covered failing ones - that gave me a lesson, how poor test cases can ruin the algorithm correctness and make you believe algorithm is free of bugs.

Now, that algorithm became a bit more complicated, I'm no longer happy how it reads. So next step of mine going to be a refactoring.

Would be interesting to know OP's progress if he finished and got all tests passing version, so we could share our algorithms and then might continue discussion on how to make them more elegant.

 It is sorta covered in the JavaRanch Style Guide.