Raghav - 1 year ago 49

Java Question

I'm just a beginner. I came across this question for which my code fails to satisfy all/most of the test cases.

Question:

Given an array of numbers, find the number of non-empty sub-arrays in which the minimum and maximum element are identical.

Example:

Input: Array = [1, 1, 3]

Output: 4

Explanation:

The required sub-arrays are [1], [1], [3], [1,1]

My solution:

Sort the array and solve the problem.

Code:

`for(int i = 0; i < testCases; i++){`

int arraySize = in.nextInt();

int array[] = new int[arraySize];

for(int j = 0; j < arraySize; j++){

array[j] = in.nextInt();

}

temp[i] = (findSubArrays(array));

}

for(int i = 0; i < testCases; i++){

System.out.println(temp[i]);

}

private static int findSubArrays(int[] array) {

Arrays.sort(array);

//Since each element can form a sub-array of its own

int noOfSubArrays = array.length;

for(int i = 0; i < array.length-1; i++){

if(array[i] == array[i+1]){

noOfSubArrays++;

}

}

return noOfSubArrays;

}

Answer Source

So you're sorting the array to keep begin points and end points adjacent so you don't need a nested traversal. That makes sense. The problem is that you're counting adjacent duplicates, but what you really need is `T(n)`

, or the triangle number of consecutive duplicates. Consider a simple scenario:

```
[1, 1, 1]
```

Your algorithm returns `5`

, but there are actually 6 subsets (by start & end index):

```
0, 0
0, 1
0, 2
1, 1
1, 2
2, 2
```

So let's update the algorithm to calculate the triangle number of each sequence:

```
private static int findSubArrays(int... array) {
Arrays.sort(array);
int sequenceCount = 0;
int total = 0;
for (int i = 0; i < array.length + 1; i++) {
if (i == array.length || (i > 0 && array[i] != array[i - 1])) {
total += triangle(sequenceCount);
sequenceCount = 0;
}
sequenceCount++;
}
return total;
}
private static int triangle(int n) {
return (n * (n + 1)) / 2;
}
```

Now calling `findSubArrays(1, 1, 1)`

returns `6`

and `findSubArrays(1, 1, 3)`

returns `4`

.