CODEWITHSUNDEEP
javaarraysalgorithm
Chaitanya
Chaitanya

Reputation: 3638

Improve performance of competitive programming question

There are N bulbs from 1 to N in a series circuit. An array denotes the bulb number from 0 to (N-1). Initially all bulbs are turned off and are switched on from index 0 of array. We need to count the number of instances for which the bulbs are switched on in series circuit.

For example :

A=[2,1,3,5,4] should return 3

Explanation :-
Instant     Bulb number on      All bulbs in series switched on
0               2                   false
1               1,2                 true
2               1,2,3               true
3               1,2,3,5             false
4               1,2,3,4,5           true

So there are 3 instances where the bulbs are switched on. Count is 3.

My approach

  1. Iterate over the indexes of array
  2. Take slice of array from 0 to index
  3. Sort the array
  4. Check whether array has all bulbs from 0 to index-1 switched on
  5. Count the number of instances.

My solution runs perfectly fine, but has a time complexity of O(n2). My solution is as follows

public int solution(int[] A) {
    // write your code in Java SE 8
    int counter = 0;

    for (int i = 0; i < A.length; i++) {
        int[] intermediate = Arrays.copyOfRange(A, 0, i);
        Arrays.sort(intermediate);

        if(checkIfOrdered(intermediate))
            counter++;
    }
    return counter;
}

private static boolean checkIfOrdered(int[] intermediate) {
    boolean flag = true;
    for (int i = 0; i < intermediate.length; i++) {
        if(intermediate[i] != (i +1) ){
            flag = false;
            break;
        }
    }
    return flag;
}

Can somebody please point out as to what can be done to improve the performance of my code ? Any pointers will be highly helpful !!!

Upvotes: 0

Views: 147

Answers (2)

josejuan
josejuan

Reputation: 9566

@fgb has indicated a simple criterion: will be true when max == count.

Then, you only have to calculate the maximum and count values.

public static int solution(int [] xs) {

    int max = xs[0];
    int count = 0;

    int trues = 0;

    for(int x: xs) {

        max = Math.max(max, x);
        count = count + 1;

        if(max == count)
            trues = trues + 1;

    }

    return trues;

}

Upvotes: 0

fgb
fgb

Reputation: 18569

With these problems, you can sometimes remove some of the loops needed by calculating the answer differently.

In your example, the only information that seems to be needed at each instant is the number of bulbs on, and the largest bulb number found so far.

For example:

  • At instant 1, there are 2 bulbs on and 2 is the largest number.
  • At instant 3, there are 3 bulbs on and 3 is the largest number.
  • At instant 4, there are 5 bulbs on and 5 is the largest number.

The answer is the number of times the largest number is equal to the number of bulbs on.

Upvotes: 5

Related Questions