Hackerrank "Breaking the Record" solution

Question

I have solved the hacker rank problem listed here. Given a sequence of scores, I need to count the number of times the records for the high and low scores have been broken.

Easiest way for me was to iterate the input for find the answer but i guess that would have meant O(n) complexity, so I thought of solving the problem using divide and conquer approach hoping it would reduce the complexity of the solution.

I have implemented the solution and it is working, but I am not sure whether I can reduce the complexity. Can you please review the code and provide feedback?

private static int minScore, maxScore;

static int[] breakingRecords(int[] score) {
    int firstScore = score[0];
    int[] result = new int[2];
    minScore = maxScore = firstScore;
    count(score,1, score.length - 1, result);

    return result;
}

private static void count(int[] scores, int start, int end, int[] result) {
    if(start == end || end < start) {
        int score = scores[start];
        if(score > maxScore) {
            maxScore = score;
            result[0] = result[0] + 1;
        } else if(score < minScore) {
            minScore = score;
            result[1] = result[1] + 1;
        }
        return;
    }

    int partition = (end + start) / 2;

    count(scores, start, partition, result);
    count(scores,partition + 1, end, result);

}

Answer 1

You should be consistent with your naming: int[] score vs. int[] scores.

Avoid keeping state in static variables. Either pass the state explicitly as parameters in your function calls, or use instance variables. I recommend against mutating instance variables with recursion, since you would have to think about what the call stack looks like, while keeping track of what the mutable global state looks like. Those two styles of programming just don't mix well.

You have way overcomplicated the problem. The task is inherently O(n), because you must consider all n inputs. Furthermore, this task cannot be parallelized. You must consider the inputs in sequence, so divide-and-conquer is not an effective strategy. Basically, your recursion is just a pointlessly complicated way of iterating through the array from front to back.

The following straightforward loop would be much preferable:

public static int[] brokenRecords(int[] scores) {
    int highScore = scores[0],
        lowScore = scores[0],
        highRecords = 0,
        lowRecords = 0;
    for (int i = 1; i < scores.length; i++) {
        if (scores[i] > highScore) {
            highScore = scores[i];
            highRecords++;
        }
        if (scores[i] < lowScore) {
            lowScore = scores[i];
            lowRecords++;
        }
    }
    return new int[] { highRecords, lowRecords };
}