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. Algorithms
  3. Greedy
  4. Candies
  5. Discussions

Candies

  • ykp01
     + 0 comments

    You have top solution! I had same approach except one bug, and your comment inspired me to debug it instead of rewriting to left-right-left solution.

    One improvement. You can get rid of iterating forward when searching for descending sequence. For 4 descending elements you'll get 4,3,2,1 in S array, which are the same as 1,2,3,4. For descending order on each iteration add current len_of_desc_seq to total sum. And you don't need any arrays, just keep track of current descending sequesce length.

    Time complexity O(N), space complexity O(1), single iteration over array.

    long candies(int n, vector<int> arr) {
    unsigned int descending_seq = 0;
    unsigned long sum = 0;
    unsigned int prev_c = 0;
    unsigned int prev_num_of_candies = 0;
    for (int c: arr) {
        if (c >= prev_c) {
            if (descending_seq > 0) {
                // agjust local max value if descending sequence
                // was longer than ascending
                if (descending_seq >= prev_num_of_candies) {
                    sum += 1 + descending_seq - prev_num_of_candies;
                }
                // last of descending = local minimum
                prev_num_of_candies = 1;
                descending_seq = 0;
            }
            if (c > prev_c) {
                ++prev_num_of_candies;
            } else {
                // optimal if previous value is the same
                prev_num_of_candies = 1;
            }
            sum += prev_num_of_candies;
        } else {
            ++descending_seq;
            // For 3 descending numbers in a row this summing strategy
            // will increment like sum+=1+2+3 which is the same as
            // more usual and expected sum+=3+2+1
            sum += descending_seq;
        }
        prev_c = c;
    }
    // If we finished on descending order, update last local max
    if (descending_seq >= prev_num_of_candies) {
        sum += 1 + descending_seq - prev_num_of_candies;
    }
    return sum;
}