Count the number of distinct subarrays

Question

I want to determine the number of distinct subarrays that can form having at most a given number of odd elements. Two subarrays are distinct if they differ at even one position. The subarray is a contiguous position of an array. Please give some suggestions to improve the time and space complexity.

Exp1:
Input: nums = [1, 2, 3, 4], k = 1
Output: 8 
Explanation: [1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [2, 3, 4]

Exp2:
Input: nums = [3, 2, 3, 4], k = 1
Output: 7 
Explanation: [3], [2], [4], [3, 2], [2, 3], [3, 4], [2, 3, 4]
Note we did not count [3, 2, 3] since it has more than k odd elements.

Exp3:
Input: nums = [3, 2, 3, 2], k = 1
Output: 5
Explanation: [3], [2], [3, 2], [2, 3], [2, 3, 2]
[3], [2], [3, 2] - duplicates
[3, 2, 3], [3, 2, 3, 2] - more than k odd elements

---

class result {
       
    static int numberOfSubarrays(int[] numbers, int k) {
        if(k == 0) return 0;
        
        boolean [] IsOdd = new boolean [numbers.length];
        
        for(int i = 0; i < numbers.length; i++){
            IsOdd[i] = numbers[i] %2 != 0;
        }
        
        HashSet<String> subs = new HashSet<String>();
        
        for(int i = 0; i < numbers.length; i++){
            StringBuilder sb = new StringBuilder();
            int oddCount = 0;
            
            for(int j = i; j < numbers.length; j++){
                if(IsOdd[j]){
                    oddCount++;
                    if(oddCount > k){ 
                        break;
                    }
                }
                sb.append(numbers[j] + " ");
                subs.add(sb.toString());
            }
        }
        return subs.size();
    }

}

---

Answer 1

Welcome to Stack Review, the first thing I see in your code is:

class result { ..your code }

Instead of result you should use Result as a classname because as specified in java_naming_conventions : Class names should be nouns, in mixed case with the first letter of each internal word capitalized.

The second thing I see in your code is:

HashSet<String> subs = new HashSet<String>();

Better to declare instead Set<String> subs = new HashSet<String>(); that guarantees more flexibility in case you want to use another implementation of theSet interface.

About performance, briefly you have a for loop where you instantiate a new StringBuilder object at every iteration like below:

for(int i = 0; i < numbers.length; i++){
   StringBuilder sb = new StringBuilder();
   ...other instructions
   sb.append(numbers[j] + " ");
}

There is a debated alternative to this scenario corresponding to instantiate one single StringBuilder object with a fixed capacity and resetting its length at every iteration of the loop with the StringBuilder.setLength method like below:

StringBuilder sb = new StringBuilder(Arrays.toString(numbers).length());
for(int i = 0; i < numbers.length; i++){
   ...other instructions
   sb.setLength(0);
}

For every testcase I set the capacity of the StringBuilder object to the length of the String representation of the initial array like [1, 2, 3, 4] that is the maximal string length the StringBuilder will contain.

Update after @TorbenPutkonen comment : better to use StringBuilder.setLength(0) at the beginning of the loop to improve readibility of the code, so the reader has a clear vision of the state of the StringBuilder at the beginning and not at the end.