K Spike - rFronteddu/general_wiki GitHub Wiki

A k-Spike is an element that satisfies both the following conditions:

• There are at least k elements from indices (0, i-1) that are less than prices[i] .
• There are at least k elements from indices (i+1, n-1) that are less than prices[i].

Count the number of k-Spikes in the given array.

We can approach the problem by precomputing how many elements on the left side and right side of each index i are less than prices[i].

Steps:

1. Left/Right-side Count: For each element prices[i], compute how many elements to the left/right of i are smaller than prices[i].
2. Result: For each i, check if both the left-side count and right-side count are at least k. If yes, then prices[i] is a k-Spike.

Algorithm:

• Traverse the Array:
  • Use two passes: one to compute the left-side counts and one to compute the right-side counts.
• Count Elements:
  • While traversing the array, maintain a sorted data structure (like a balanced binary search tree or a sorted array) to keep track of the elements seen so far, so you can efficiently count how many are smaller than prices[i] for both the left and right sides.

TreeSet: We use TreeSet to maintain a sorted set of elements.

• The method headSet(x) efficiently returns a view of the elements that are strictly less than x, which allows us to count how many elements on the left or right are smaller than prices[i].

Time Complexity:

• The solution runs in O(n log n) because each insertion and query in the TreeSet takes logarithmic time.
• We perform this operation n times for both left-side and right-side counts.

Space Complexity:

• The space complexity is O(n) due to the TreeSet used for counting and the arrays leftCount[] and rightCount[].

import java.util.TreeSet;

class Solution {
    public int countKSpikes(int[] prices, int k) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;
        
        // Arrays to store counts of elements less than prices[i] from left and right
        int[] leftCount = new int[n];
        int[] rightCount = new int[n];

        // TreeSet to maintain elements for counting less-than on the left side
        TreeSet<Integer> leftSet = new TreeSet<>();
        
        // Compute the left side counts
        for (int i = 0; i < n; i++) {
            // Count how many elements in leftSet are less than prices[i]
            leftCount[i] = leftSet.headSet(prices[i]).size();
            // Add current element to the leftSet for future indices
            leftSet.add(prices[i]);
        }

        // TreeSet to maintain elements for counting less-than on the right side
        TreeSet<Integer> rightSet = new TreeSet<>();
        
        // Compute the right side counts
        for (int i = n - 1; i >= 0; i--) {
            // Count how many elements in rightSet are less than prices[i]
            rightCount[i] = rightSet.headSet(prices[i]).size();
            // Add current element to the rightSet for future indices
            rightSet.add(prices[i]);
        }

        // Count the number of k-Spikes
        int kSpikeCount = 0;
        for (int i = 0; i < n; i++) {
            if (leftCount[i] >= k && rightCount[i] >= k) {
                kSpikeCount++;
            }
        }

        return kSpikeCount;
    }
}