• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

How to remove the maximum values from an array of integers?

 
Ranch Hand
Posts: 77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The correct implementation should receive an array of int values and return a copy of a given array with all local maxima removed in it. The original array must not be changed.

Local maximum is an element that is bigger that any of its neighbour elements. You should remove elements that are local maxima in the original array.

Details:

The size of given array is guaranteed to be more than 1.
Given array is guaranteed to be not null.
If the array has no local maxima, then you should return its copy without changes.
You may use java.util.Arrays.* methods.

Example1

Input array: `[18, 1, 3, 6, 7, -5]`

Output array: `[1, 3, 6, -5]`

Example2

Input array: `[-3, 2, 4, 13, 5, 12, 8]`

Output array: `[-3, 2, 4, 5, 8]`




I know how to find the maximum, but can't be removed from an array of integers.
I know that an array can't be modified, so I tried to copy the elements in another array.
I noticed that can I copy the elements who are less than his neighbors in another array and I can find the solution.

How can I copy the elements who are less than his neighbors into a new array?
 
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Cris Marinescu wrote:Example1
Input array: `[18, 1, 3, 6, 7, -5]`
Output array: `[1, 3, 6, -5]`

What is the definition of "neighbor"? I would have thought a neighbor is one immeadiately before or after a particular element.
(18 & 1) = 18
(18 & 1 & 3) = 18
(1 & 3 & 6) = 6
( 3  & 6 & 7) = 7
(6 & 7 & -5) = 7
( 7 & -5) = 7

Can you clarify?
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Cris Marinescu wrote:Example1
Input array: `[18, 1, 3, 6, 7, -5]`
Output array: `[1, 3, 6, -5]`


xx, [18], 1 = 18
18, [1], 3 = not 1
1, [3], 6 = not 3
3, [6], 7 = not 6
6, [7], -5 = 7
7, [-5], xx = not -5

Ok, that makes more sense. Not sure about the edge conditions, the first and last comparisons.
 
Cris Marinescu
Ranch Hand
Posts: 77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Exactly, a neighbor is one immediatelly before and after an element
 
Cris Marinescu
Ranch Hand
Posts: 77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


I chose to use ArrayList.
I convert the array to Array List, then I compared the elements if neighbour elements is bigger than of its neighbour elements I removed it.
Its working well. I have only one test case who I fail it:

Example:
array = new int[]{-18, 21, 3, 6, 7, 65};

expected = new int[]{-18, 3, 6, 7};

I got result [-18, 3, 6, 7, 65] which is wrong because 65 its not removed. How can I delete the last one when its bigger than previous neighbour?
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think your first set  of code was more on target. You've got to compare an element to both of it's neighbors. Except you'll need a special condition for the first and last elements that only compare one other neighbor.

You could do this with two IF statements.
or
You you could append and prepend an Integer.MIN_VALUE to the list, then there are no special cases. Start at index 1 and end at length-2.
min, -18, 21, 3, 6, 7, 65, min

OH, I forgot. Another special case is when there is only one element,  in which the MIN approach still works but the IF requires another step.
 
Cris Marinescu
Ranch Hand
Posts: 77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is it better to try to solve it with first approach without using ArrayList?
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

 
Cris Marinescu
Ranch Hand
Posts: 77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you for code, very clever approach!
When I'm tested, it failed one test:

" Tests.removeLocalMaximaTest:78 expected: <998> but was: <997> "

This is my Test Class



I see that it says in the error that was expected: <998> but was: <997>.
Indeed there is 998, I don't understand from where it's coming that error.
Can you give me some hints?
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

 
Bartender
Posts: 5465
212
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Also nice is:
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 7



 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Will still break for the case where array.length == 1, which is not one of the test cases.

Sorry, Given array length will be greater than one.
 
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Cris Marinescu wrote:
This is my Test Class
. . .
Can you give me some hints?


You could organize your test class better and break it up into many @Test cases instead of having one huge one.

The advantage of having many @Test cases is that you have a better idea of why a test failed and it's more focused on a specific problem. Your other tests could already pass but with a huge @Test method, you won't know which ones already work if an earlier assertion fails.

Yes, it's more work on the surface, to think of many different meaningful names to give to your tests but it makes understanding and troubleshooting code much easier if you have many small, focused tests rather than one "Big Ball of Mud" test.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For example, this

I don't know what the assertion on line 15 is for. Is it something you were just experimenting with? It's never going to fail unless you change line 11, so why have it there?
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The question I just asked would be reasonable if someone just had a cursory look at the test code. If you had this test instead:

Someone reading this test will know exactly what the intent of the test is. They won't have to go digging around elsewhere for context.

Try breaking up your huge @Test method to many smaller ones that clearly express the intent of each section you have blocked off.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You might also try solving this with a sliding window: https://4comprehension.com/sliding-window-stream-spliterator-in-java/
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Are you sure this is a correct expectation?

?

Why would 65 on the end be considered a local maximum? If you remove it, by the same token, wouldn't 7 then become a local maximum? And then 6 after you remove 7?

It seems to me that the first and the last elements of the array cannot be local maxima because there is only one adjacent element.
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Remember from school: finding all the local extremes on a segment [a, b] also included checking the values at a and b.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:Remember from school: finding all the local extremes on a segment [a, b] also included checking the values at a and b.


To be honest, this is the first time I've heard of this problem. Never encountered it in school. Of course, I didn't pay much attention when I was in school.
 
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:. . . finding all the local extremes . . . included checking the values at a and b.

I think that should have been specified in the original question.

Junilu Lacar wrote:. . . If you remove it, by the same token, wouldn't 7 then become a local maximum? . . .

I think you are only allowed one pass through the array. Otherwise the whole exercise changes to emptying the array local maxima first.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
From what I've seen/learned, a local maximum is any element that doesn't have at least one neighboring element that is greater. In other words, if there's at least one neighboring element with a greater value, the element is not a local maximum. And yes, it's a one-pass operation.
reply
    Bookmark Topic Watch Topic
  • New Topic