Contiguous Subarrays

You are given an array arr of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfill the following conditions:

The value at index i must be the maximum element in the contiguous subarrays, and
These contiguous subarrays must either start from or end on index i.

Signature int[] countSubarrays(int[] arr) Input

Array arr is a non-empty list of unique integers that range between 1 to 1,000,000,000
Size N is between 1 and 1,000,000

Output An array where each index i contains an integer denoting the maximum number of contiguous subarrays of arr[i]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Example:
arr = [3, 4, 1, 6, 2]
output = [1, 3, 1, 5, 1]
Explanation:

    For index 0 - [3] is the only contiguous subarray that starts (or ends) with 3, and the maximum value in this subarray is 3.
    For index 1 - [4], [3, 4], [4, 1]
    For index 2 - [1]
    For index 3 - [6], [6, 2], [1, 6], [4, 1, 6], [3, 4, 1, 6]
    For index 4 - [2]

So, the answer for the above input is [1, 3, 1, 5, 1]

Solution

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
import java.io.*; 
import java.util.*;
// Add any extra import statements you may need here


class Main {

  // Add any helper functions you may need here
  
  
  int[] countSubarrays(int[] arr) {
    int n = arr.length;
    Stack<Integer> stack = new Stack<>();
    
    int[] left = new int[n];
    for (int i = 0; i < n; i++) {
      while (stack.size() > 0 && arr[stack.peek()] < arr[i]) {
           left[i] += left[stack.pop()];
      }
      left[i]++;
      stack.push(i);
    }
    stack.clear();
    int[] right = new int[n];
    // [3, 4, 1, 6, 2]
    for (int i = n - 1; i >= 0; i--) {
      while (stack.size() > 0 && arr[stack.peek()] < arr[i]) {
        right[i] += right[stack.pop()];
      }
      right[i]++;
      stack.push(i);
    }
    
    int[] res = new int[n];
    
    for (int i = 0; i < n; i++) {
      res[i] = left[i] + right[i] - 1;
    }
    
    return res;
  }  
  

  int[] countSubarrays2(int[] arr) {
    // Write your code here
    int n = arr.length;
    int[] res = new int[n];
    
    for (int i = 0; i < n; i++) {
      res[i] = 1;
      res[i] += countSubarraysLeft(i, arr);
      res[i] += countSubarraysRight(i, arr);
      
    }
    return res;
  }
  
  int countSubarraysLeft(int i, int[] arr) {
    
    int count = 0;
    int j = i - 1;
    while (j >= 0 && arr[j] < arr[i]) {
      j--;
      count++;
    } 
    
    return count;
  }
  
  int countSubarraysRight(int i, int[] arr) {
    
    int count = 0;
    int j = i + 1;
    while (j < arr.length && arr[j] < arr[i]) {
      j++;
      count++;
    } 
    
    return count;
  }












  // These are the tests we use to determine if the solution is correct.
  // You can add your own at the bottom.
  int test_case_number = 1;
  void check(int[] expected, int[] output) {
    int expected_size = expected.length; 
    int output_size = output.length; 
    boolean result = true; 
    if (expected_size != output_size) {
      result = false;
    }
    for (int i = 0; i < Math.min(expected_size, output_size); i++) {
      result &= (output[i] == expected[i]);
    }
    char rightTick = '\u2713';
    char wrongTick = '\u2717';
    if (result) {
      System.out.println(rightTick + " Test #" + test_case_number);  
    }
    else {
      System.out.print(wrongTick + " Test #" + test_case_number + ": Expected ");
      printIntegerArray(expected); 
      System.out.print(" Your output: ");
      printIntegerArray(output);
      System.out.println();
    }
    test_case_number++;
  }
  void printIntegerArray(int[] arr) {
    int len = arr.length; 
    System.out.print("[");
    for(int i = 0; i < len; i++) {
      if (i != 0) {
        System.out.print(", ");
      }
      System.out.print(arr[i]);
    }
    System.out.print("]");
  }
  public void run() {
    int[] test_1 = {3, 4, 1, 6, 2};
    int[] expected_1 = {1, 3, 1, 5, 1};
    int[] output_1 = countSubarrays(test_1);
    check(expected_1, output_1);
    
    int[] test_2 = {2, 4, 7, 1, 5, 3};
    int[] expected_2 = {1, 2, 6, 1, 3, 1};
    int[] output_2 = countSubarrays(test_2);
    check(expected_2, output_2);
  
    // Add your own test cases here
    
  }
  public static void main(String[] args) {
    new Main().run();
  }
}

Solution#

Solution