Given the changes to stock price over a period of time as an array of distinct integers, count the number of spikes in the stock price which are counted as K-Spikes.
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 the price[i].
- There are at least K elements from indices (i+1, n-1) that are less than the price[i].
Examples:
Input: price = [1, 2, 8, 5, 3, 4], K = 2
Output: 2
Explanation: There are 2 K-Spikes:
• 8 at index 2 has (1, 2) to the left and (5, 3, 4) to the right that are less than 8.
• 5 at index 3 has (1, 2) to the left and (3, 4) to the right that are less than 5.Input: price = [7, 2, 3, 9, 7, 4], K = 3
Output: 0
Explanation: There is no K-spike possible for any i. For element 9 there are at least 3 elements smaller than 9 on the left side but there are only 2 elements that are smaller than 9 on the right side.
Naive approach: The basic way to solve the problem is as follows:
The idea is to check for every element of the price array whether it is a K-spike or not.
- To check we calculate the number of elements that are smaller than prices[i] in the range [0 …… i-1]
- Calculate the number of elements that are smaller than the price[i] in the range[i+1 …… N] by again traversing using loops
- After that if the given condition is satisfied then the price[i] is K-spike then we increment our answer.
Time complexity: O(N2)
Auxillary space: O(1)
Efficient approach: To solve the problem follow the below idea:
In the naive approach we have traversed the array again for finding count of smaller elements till i-1 or from i+1, but how about precalculating the number of elements that are smaller than price[i] in range[0…… i-1] and also in range[i+1…..N) and storing them in an prefix and suffix array respectively.
Follow the steps to solve the problem:
- We construct two array’s prefix and suffix, prefix[i] denotes number of elements that are smaller than price[i] in [0……i-1] and suffix[i] denotes the number of elements that are smaller than price[i] in [i+1 …… N).
- To construct prefix array we maintain a ordered set(Policy based data structure) in which elements till index i-1 already present in set so we can find the position of price[i] in ordered set by using order_of_key function which gives number of items strictly smaller than price[i] then we just put this value at prefix[i] and at last we push price[i] in set.
- To construct suffix array we traverse the price array backwards and do the similar thing that we have done for prefix array.
- Now we have prefix and suffix array in our hand then we traverse the price aray and check if both prefix[i] and suffix[i] are at least K then we increment our answer.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>Â
using namespace std;using namespace __gnu_pbds;Â
template <typename T>using pbds = tree<T, null_type, less<T>, rb_tree_tag,                  tree_order_statistics_node_update>;Â
// Function to calculate the number of// spikes in price arrayint CalculateNumberOfKSpikes(vector<int>& price, int k){Â Â Â Â int n = price.size();Â
    // Decalare ordered set    pbds<int> st1, st2;Â
    // Initialize a variable for storing our    // number of K-spikes    int countOfKspikes = 0;Â
    // Declaring prefix and suffix array where    // prefix[i] denotes number of elements    // that are smaller than price[i] in    // [0......i-1] and suffix[i] denotes the    // number of elements that are smaller than    // price[i] in [i+1 ...... N).    vector<int> prefix(n + 1, 0), suffix(n + 1, 0);    for (int i = 0; i < n; i++) {Â
        // Calculate the number of elements that        // are smaller than price[i] using        // order_of_key function        prefix[i] = st1.order_of_key(price[i]);Â
        // Insert current price[i] to contribute in        // next iteration        st1.insert(price[i]);    }Â
    for (int i = n - 1; i >= 0; i--) {Â
        // Calculate the number of elements that        // are smaller than price[i] using        // order_of_key function        suffix[i] = st2.order_of_key(price[i]);Â
        // Insert current price[i] to contribute        // in next iteration        st2.insert(price[i]);    }Â
    for (int i = 0; i < n; i++) {Â
        // If prefix and suffix are atleast K than        // current element is k-spike        if (prefix[i] >= k && suffix[i] >= k) {            countOfKspikes++;        }    }    return countOfKspikes;}Â
// Drivers codeint main(){Â Â Â Â vector<int> price = { 1, 2, 8, 5, 3, 4 };Â Â Â Â int k = 2;Â
    int countOfKspikes = CalculateNumberOfKSpikes(price, k);Â
    // Function Call    cout << countOfKspikes;    return 0;} |
Java
import java.util.TreeSet;Â
public class Main {    // Function to calculate the number of spikes in price array    static int calculateNumberOfKSpikes(int[] price, int k) {        int n = price.length;Â
        // Declare ordered sets        TreeSet<Integer> st1 = new TreeSet<>();        TreeSet<Integer> st2 = new TreeSet<>();Â
        // Initialize a variable for storing our number of K-spikes        int countOfKSpikes = 0;Â
        // Declaring prefix and suffix arrays where        // prefix[i] denotes the number of elements        // that are smaller than price[i] in        // [0......i-1] and suffix[i] denotes the        // number of elements that are smaller than        // price[i] in [i+1 ...... N).        int[] prefix = new int[n + 1];        int[] suffix = new int[n + 1];Â
        for (int i = 0; i < n; i++) {            // Calculate the number of elements that            // are smaller than price[i] using            // lower() function            prefix[i] = st1.headSet(price[i]).size();Â
            // Insert current price[i] to contribute in            // the next iteration            st1.add(price[i]);        }Â
        for (int i = n - 1; i >= 0; i--) {            // Calculate the number of elements that            // are smaller than price[i] using            // lower() function            suffix[i] = st2.headSet(price[i]).size();Â
            // Insert current price[i] to contribute            // in the next iteration            st2.add(price[i]);        }Â
        for (int i = 0; i < n; i++) {            // If prefix and suffix are at least K, then            // the current element is a K-spike            if (prefix[i] >= k && suffix[i] >= k) {                countOfKSpikes++;            }        }Â
        return countOfKSpikes;    }Â
    // Driver code    public static void main(String[] args) {        int[] price = {1, 2, 8, 5, 3, 4};        int k = 2;Â
        int countOfKSpikes = calculateNumberOfKSpikes(price, k);Â
        // Function Call        System.out.println(countOfKSpikes);    }} |
Output
2
Time Complexity: O(N*logN)
Auxillary space: O(N), where N is the size of the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
