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); }} |
2
Time Complexity: O(N*logN)
Auxillary space: O(N), where N is the size of the array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
