2
\$\begingroup\$

Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

Examples:

Input:

arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3

Output:

3 3 4 5 5 5 6

Input:

arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}
k = 4

Output:

10 10 10 15 15 90 90

Looking for code-review, best practices, and optimizations.

public class MaxOfSubArrays {

    private MaxOfSubArrays() { }
    

    public static List<Integer> maxList(int[] a, int k)   {
        if (k <= 0) {
            throw new IllegalArgumentException("The value of k should atleast be 1.");
        }
        
        final Deque<Integer> deque = new ArrayDeque<Integer>();
        final List<Integer> result = new ArrayList<Integer>();
        
        int i;
        for (i = 0; i < k; i++) {
            while (!deque.isEmpty() && a[deque.peek()] <= a[i]) {
                deque.removeFirst();
            }
            deque.addLast(i);
        }
        
        
        for (; i < a.length; i++) {
            result.add(a[deque.peek()]);
            
            while (!deque.isEmpty() && deque.peek() <= i - k) {
                deque.removeFirst();
            }
            
            while (!deque.isEmpty() && a[deque.peek()] <= a[i]) {
                deque.removeFirst();
            }
            
            deque.addLast(i);
        }

        result.add(a[deque.peek()]);
        return result;
    }
}


public class MaxOfSubArraysTest {

    @Test
    public void test1() {
        int[] a1 = {1, 2, 3, 4, 5, 6};
        List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(3, 4, 5, 6));
        assertTrue(list1.equals(MaxOfSubArrays.maxList(a1, 3)));
    }
    
    @Test
    public void test2() {
        int[] a2 = {6, 5, 4, 3, 2, 1};
        List<Integer> list2 = new ArrayList<Integer>(Arrays.asList(6, 5, 4, 3));
        assertTrue(list2.equals(MaxOfSubArrays.maxList(a2, 3)));
    }
    
}
\$\endgroup\$
4
\$\begingroup\$

Here you are using a few structures which I feel are not the right tool for the job.

Firstly, you are given an array of int, but you are returning a List<Integer>. I dislike List<Integer>, but even worse than using a List for primitives, is using a mixture of them. Be consistent!

The dueue is a confusing concept. It is worse because you use a for-loop in a non-traditional way, with the loop-variable declared outside the loop, and you reuse it later. You don't have any comments explaining how you use it.

At this point, I have looked through the requirements, I have figured out how I would do it. I can see that your strategy may have some advantages, if it does what I think it does, but it is complicated, and hard to read. So, I am giving up....

Code Review not successful, not commented enough, not enough background information.

\$\endgroup\$
1
  • \$\begingroup\$ I have to agree, the code is very hard to understand. Horrible variable names doesn't help at all. Deque<Integer> deque... well of course it's a deque! \$\endgroup\$ – Simon Forsberg Jun 27 '14 at 23:33
3
\$\begingroup\$

Leaving aside the formatting and style, and having a look at the algorithm, it does not always work.

Say we have

arr[] = {6,3,4,1,1,2,5,6};
k = 3;

As far as I can see, we should get

6,3,4 => 6
3,4,1 => 4
4,1,1 => 4
1,1,2 => 2
1,2,5 => 5
2,5,6 => 6

but we get

6, 3, 4, 2, 5, 6

The problem seems to be intrinsic in the algorithm.

After the first loop to k we end up with a queue containing

H     T
6, 3, 4

6 was placed in first and nothing was larger than or equal to it. All others added to tail

We add 6 to result.

Starting at i = 2 we remove the head element if it has an index <= i-2 (0). So we remove 6

H  T
3, 4

the next number is 1.
The head value (3) > 1, so do not remove it and we add 1 to end of queue.

H     T
3, 4, 1

Add 3 to result, even though 4 is the largest in this subset.

We have no guarantees about the order of anything in the queue other than the first was the largest of the initial group. Once the first (6) is removed, there is no reason for the new head to be the largest.

Looking at the problem, (and I am open to correction on this), the simplest way to solve it seems to finding the max of moving window on the src array

public int[] findMaxValues(int[] src, int k){
    int[] ret = new int[src.length - k + 1];

    for(int index = 0; index < ret.length; index++){
        ret[index]= findMax(src, index, k);
    }

    return ret;
}

private int findMax(int[] src, int start, int count){
    int max = 0;
    for(int index = start; index < start + count; index++){
        if(src[index] > max){
                max = src[index];
        }
    }

    return max;
}
\$\endgroup\$
2
  • \$\begingroup\$ Just a note that you can make all parameters to both methods, as well as ret, final. The JVM can do a few tiny optimizations (calculate start + count just once per method call, for example), and it can also help catching bugs if the code needs to change. Also, you can abbreviate index to just i for your loop indexes. Just a stylistic change, but a pretty common idiom and widely understood. \$\endgroup\$ – cbojar Jun 30 '14 at 16:08
  • \$\begingroup\$ @cbojar Thanks. It's one of the bonuses of reviewing; I get to improve my (pretty basic) java. \$\endgroup\$ – AlanT Jul 1 '14 at 13:20
2
\$\begingroup\$

Tests

I'll just concentrate on test because there is something that must be done. Tests are as much important as your code. You should put as much effort in it as your code. Use relevant methods name, use relevant variables names and the quality of your test should be as good as your code. When I read a test, I should know what you are testing.

@Test
public void test1() {
    int[] a1 = {1, 2, 3, 4, 5, 6};
    List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(3, 4, 5, 6));
    assertTrue(list1.equals(MaxOfSubArrays.maxList(a1, 3)));
}

test1 is really a bad name. It represent nothing at all. Is it for testing a regular case of your algorithm, is it for an exceptional case ? a1 say nothing at all and the same is true for list1. See the corrections below :

@Test
public void normalTestCase() {
    int[] input = {1, 2, 3, 4, 5, 6};
    List<Integer> expected = new ArrayList<Integer>(Arrays.asList(3, 4, 5, 6));
    assertTrue(expected.equals(MaxOfSubArrays.maxList(input, 3)));
}

Another factor that make your tests almost useless is that it isn't testing everything in the method. 2 tests cases for your algorithm seems not enough. There is at least 1 missing test case where k == 0. I should have seen :

@Test(expected = IllegalArgumentException.class)
public void exceptionWhenKIsNotValid() {
    int[] input = {1, 2, 3, 4, 5, 6};
   MaxOfSubArrays.maxList(input, 0);
}

You should be testing for null arrays, empty arrays and every exceptional cases. This will help you clarify what the method should and should not to do. It would help us understand your code too since those tests would explain a lot your codes. As it stand at the method, two tests cases for your algorithm is not helping anyone at all.

\$\endgroup\$
1
\$\begingroup\$

The two answers already given cover most of the issues you have with your code as written. You have over-engineered a solution for the problem, which has led to it being hard to read and, as AlanT notes, wrong. You work hard to use data structures in this solution, even though they are completely unnecessary, and I wonder what source you got either your solution or the idea for your solution from. Rather than point out where the problems are, which rolfl did, or show the solution, as AlanT did, let me try to break down your proposed solution to see where we can improve the problem solving for next time.

First, this problem is relatively simple, so we can pencil-and-paper (at least) the samples before we start writing the program to make sure we really get the algorithm. I'm going to leave this step as an exercise to the reader.

Next, let's look at the method progressively in chunks:

public static List<Integer> maxList(int[] a, int k)   {
    if (k <= 0) {
        throw new IllegalArgumentException("The value of k should atleast be 1.");
    }

I'm going to pass over whether this should or should not be a static method. We take a primitive int array, but return a List of Integer object. Generally, we should aim to be consistent between what we accept and what we return. There are large, gaping holes in this rule of thumb, but here it applies. The code calling us is going to be happily working with primitive arrays, so we should be happy to return primitive arrays (int[] in this case). Below that, we do a range check. This is good, but incomplete. We make sure k is positive, but we should also check whether k <= a.length. What happens if my subsets are larger than the whole array? Unexpected runtime errors.


    final Deque<Integer> deque = new ArrayDeque<Integer>();
    final List<Integer> result = new ArrayList<Integer>();

Here you declare a Deque<Integer> and an ArrayList<Integer>. The name deque does not clearly define the purpose of this variable. Indeed, reading through the rest of the code, the purpose of this variable is not clearly discernible. Since a Deque is a double-ended queue, then perhaps it is used as a sliding window along the array? Then I notice what is missing: any type of variable for holding a temporary max value. This holder should accompany wherever the window is declared since they are logically associated in the algorithm.

As to result, the name is not great, but is acceptable as it is a holder for the result. The question is why result is an List<Integer>? Lists are good for, among other uses, when we don't know the final size of a chunk of data. They can expand automatically as we add data, and can transparently handle removed data. But in this case, the size of the result is deterministic. From our pencil-and-paper analysis, we can see that the result is shorter than the source array. It's probably shorter relative to k, since k is our only other input. After a little fiddling and quick math, we can see that the size of the output is equal to a.length - k + 1. So we can know the size ahead of time. Since we've already said that our outputs should generally mirror our inputs, we can use that data structure that is primitive, ordered, and has a defined length: int[].


    int i;
    for (i = 0; i < k; i++) {
        while (!deque.isEmpty() && a[deque.peek()] <= a[i]) {
            deque.removeFirst();
        }
        deque.addLast(i);
    }

Ok, we declare a loop variable outside the loop? Unusual. We loop here from 0..k ... meaning that this is only for the first subset. When we did our pencil-and-paper analysis, did we have a different process for the first subset? Not in mine. This does start to give the first clues as to the purpose of deque though. In the first iteration of the outer for-loop, deque is empty, so we skip the while-loop, and add the index 0 to the end of the deque. Next iteration, the deque is not empty, so is a[0] <= a[1]? If so, remove 0. Otherwise, do nothing. Add 1 to the deque. So the deque is accumulating indexes where the values are descending? It isn't really a sliding window, then, and it isn't holding the max value either. It's holding a series of indexes, where the index at the front of the deque is the index of the largest value in the source array (maybe?). It may also contain indexes of smaller values that come after the initial index. It definitely contains index k-1.


    for (; i < a.length; i++) {
        result.add(a[deque.peek()]);

        while (!deque.isEmpty() && deque.peek() <= i - k) {
            deque.removeFirst();
        }

        while (!deque.isEmpty() && a[deque.peek()] <= a[i]) {
            deque.removeFirst();
        }

        deque.addLast(i);
    }

So we are reusing index i again, starting at value k. We could just as easily do int i = k in the for-loop declaration (if we declare int i = 0 in the other for-loop declaration as well). This loop handles all of the rest of the subsets, so this is the real meat of the method. The first thing we do when we enter the loop is add the value of the first index in the deque to the result. Right...um. So we are adding the result of the previous loop to result array as the first action in the second loop? The logic for the first subset has now leaked into the logic for the rest of the subsets. This can get very messy. Let's say I want to be helpful and I say "Hey, this line can just as easily be done at the end of this loop!" so I move it and, bam!, mega-brokeness.

Next, we appear to be using a while-loop to "slide" our "sliding window" by removing all indexes outside of the subset. This should only ever loop once, since at most we should be sliding the subset by one element. It could run 0 times if we've already removed the leading index.

The rest of the loop is exactly the same as the first for-loop, so we have some duplication here.

Something important to note here is that we are using deque.peek() and deque.removeFirst() quite a bit. They are also being used in rather unconventional ways (usually we use deque.peek() sparingly for testing the top element, and here we are ignoring the result of deque.removeFirst()). When we are using a data structure in a way that is not typical, we can consider this to be a yellow flag. Maybe we are doing something pretty unusual here, but more likely we are misusing the data structure and there may be a better approach.


    result.add(a[deque.peek()]);
    return result;

We've seen that first line before, which means potentially more duplication. Finally, we return. All done!


You didn't really think we were all done, did you? As I was writing this answer, Marc-Andre beat me to some of the points I was going to make, but there are still a few more.

@Test
public void test1() {
    int[] a1 = {1, 2, 3, 4, 5, 6};
    List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(3, 4, 5, 6));
    assertTrue(list1.equals(MaxOfSubArrays.maxList(a1, 3)));
}

@Test
public void test2() {
    int[] a2 = {6, 5, 4, 3, 2, 1};
    List<Integer> list2 = new ArrayList<Integer>(Arrays.asList(6, 5, 4, 3));
    assertTrue(list2.equals(MaxOfSubArrays.maxList(a2, 3)));
}

Test names are bad. Also, the window size (aka k) should be declared as a variable as well. With all the parens, the 3 gets lost in the noise. More bad names a2 and list2, maybe inputArray and expectedResult, respectively?

Most important, your test cases fall short. You make up your own test inputs, which is fine, but you are given two examples in your problem definition. When you are given a sample input with the correct output, that screams "MAKE ME A TEST!" Sample inputs are usually a little more complex and are often written to trip up common bad algorithm implementations. Your tests only test sorted arrays, whereas the examples are unsorted and larger. Samples are the easiest tests to write, and should be the first tests written.

\$\endgroup\$

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.