We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Kindergarten Adventures
  5. Discussions

Kindergarten Adventures

  • longvatrong111
     + 2 comments

    My O(n) solution in C++. Here is my idea: 1. For each value of t[i], count all sastified starting points then store in an array. 2. Search for max element in array then return the index. To store and search effciently, you may try the problem Array Manipulation in Data structure - hard - array

    int solve(vector<int> t) {
    int n = t.size();
    /* n < 10^5
    Must move to heap memory
    */
    int arr[n+1] = {0}; 
    
    for (int i = 0; i < n; ++i) {
        if (t[i] - i > 0) {
            /* t[i] > i
            The start point is included in (i+1,n - (t[i]-i))
            Add 1 in the count array when go into the interval
            Remove 1 when go out the interval
            */
            arr[i+1] += 1;
            arr[n - (t[i]-i) + 1] -= 1;
        }
        else {
            /* t[i] <= i
            The start point is included in (0,i - t[i]) and (i+1,n-1)
            Add 1 in the count array when go into the interval
            Remove 1 when go out the interval
            */
            arr[0] += 1;
            arr[i - t[i] + 1] -= 1;
            arr[i+1] += 1;
            arr[n] -= 1;
        } 
    }
    
    int index = 0;
    int count = 0;
    int max = 0;
    
    for (int i = 0; i < n; ++i) {
        count += arr[i];
        if (count > max) {
            max = count;
            index = i + 1;
        } 
    }
    
    return index;
}