Number of K-Spikes in Stock Price Array - Coding

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.

C++

#include <iostream>
#include <vector>
using namespace std;

int countKSpikes(vector<int>& price, int K)
{
    int n = price.size();
    // Initialize left and right arrays to store the count
    // of smaller elements
    vector<int> left(n, 0);
    vector<int> right(n, 0);

    // Preprocess left array
    for (int i = 1; i < n; ++i) {
        int count = 0;
        for (int j = 0; j < i; ++j) {
            if (price[j] < price[i]) {
                count++;
            }
        }
        left[i] = count;
    }

    // Preprocess right array
    for (int i = n - 2; i >= 0; --i) {
        int count = 0;
        for (int j = i + 1; j < n; ++j) {
            if (price[j] < price[i]) {
                count++;
            }
        }
        right[i] = count;
    }

    // Count K-spikes
    int spikeCount = 0;
    for (int i = 0; i < n; ++i) {
        if (left[i] >= K && right[i] >= K) {
            spikeCount++;
        }
    }

    return spikeCount;
}

// Example usage:
int main()
{
    vector<int> price1 = { 1, 2, 8, 5, 3, 4 };
    int K1 = 2;
    cout << "Number of K-spikes: "
         << countKSpikes(price1, K1) << endl; // Output: 2

    vector<int> price2 = { 7, 2, 3, 9, 7, 4 };
    int K2 = 3;
    cout << "Number of K-spikes: "
         << countKSpikes(price2, K2) << endl; // Output: 0

    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {

    static int countKSpikes(List<Integer> price, int K)
    {
        int n = price.size();
        // Initialize left and right arrays to store the
        // count of smaller elements
        int[] left = new int[n];
        int[] right = new int[n];

        // Preprocess left array
        for (int i = 1; i < n; ++i) {
            int count = 0;
            for (int j = 0; j < i; ++j) {
                if (price.get(j) < price.get(i)) {
                    count++;
                }
            }
            left[i] = count;
        }

        // Preprocess right array
        for (int i = n - 2; i >= 0; --i) {
            int count = 0;
            for (int j = i + 1; j < n; ++j) {
                if (price.get(j) < price.get(i)) {
                    count++;
                }
            }
            right[i] = count;
        }

        // Count K-spikes
        int spikeCount = 0;
        for (int i = 0; i < n; ++i) {
            if (left[i] >= K && right[i] >= K) {
                spikeCount++;
            }
        }

        return spikeCount;
    }

    // Example usage:
    public static void main(String[] args)
    {
        List<Integer> price1 = new ArrayList<>();
        price1.add(1);
        price1.add(2);
        price1.add(8);
        price1.add(5);
        price1.add(3);
        price1.add(4);
        int K1 = 2;
        System.out.println(
            "Number of K-spikes: "
            + countKSpikes(price1, K1)); // Output: 2

        List<Integer> price2 = new ArrayList<>();
        price2.add(7);
        price2.add(2);
        price2.add(3);
        price2.add(9);
        price2.add(7);
        price2.add(4);
        int K2 = 3;
        System.out.println(
            "Number of K-spikes: "
            + countKSpikes(price2, K2)); // Output: 0
    }
}

Python

def countKSpikes(price, K):
    n = len(price)
    # Initialize left and right arrays to store the count of smaller elements
    left = [0] * n
    right = [0] * n

    # Preprocess left array
    for i in range(1, n):
        count = 0
        for j in range(i):
            if price[j] < price[i]:
                count += 1
        left[i] = count

    # Preprocess right array
    for i in range(n - 2, -1, -1):
        count = 0
        for j in range(i + 1, n):
            if price[j] < price[i]:
                count += 1
        right[i] = count

    # Count K-spikes
    spike_count = 0
    for i in range(n):
        if left[i] >= K and right[i] >= K:
            spike_count += 1

    return spike_count


# Example usage:
price1 = [1, 2, 8, 5, 3, 4]
K1 = 2
print("Number of K-spikes:", countKSpikes(price1, K1))  # Output: 2

price2 = [7, 2, 3, 9, 7, 4]
K2 = 3
print("Number of K-spikes:", countKSpikes(price2, K2))  # Output: 0

JavaScript

function countKSpikes(price, K) {
    let n = price.length;
    // Initialize left and right arrays to store the count of smaller elements
    let left = new Array(n).fill(0);
    let right = new Array(n).fill(0);

    // Preprocess left array
    for (let i = 1; i < n; ++i) {
        let count = 0;
        for (let j = 0; j < i; ++j) {
            if (price[j] < price[i]) {
                count++;
            }
        }
        left[i] = count;
    }

    // Preprocess right array
    for (let i = n - 2; i >= 0; --i) {
        let count = 0;
        for (let j = i + 1; j < n; ++j) {
            if (price[j] < price[i]) {
                count++;
            }
        }
        right[i] = count;
    }

    // Count K-spikes
    let spikeCount = 0;
    for (let i = 0; i < n; ++i) {
        if (left[i] >= K && right[i] >= K) {
            spikeCount++;
        }
    }

    return spikeCount;
}

// Example usage:
let price1 = [1, 2, 8, 5, 3, 4];
let K1 = 2;
console.log("Number of K-spikes: " + countKSpikes(price1, K1)); // Output: 2

let price2 = [7, 2, 3, 9, 7, 4];
let K2 = 3;
console.log("Number of K-spikes: " + countKSpikes(price2, K2)); // Output: 0

Output

Number of K-spikes: 2
Number of K-spikes: 0

Time complexity: O(N²)
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++

#include <iostream>
#include <set>
#include <vector>

using namespace std;

// Function to calculate the number of spikes in price array
int calculateNumberOfKSpikes(const vector<int>& price,
                             int k)
{
    int n = price.size();

    // Declare ordered sets
    set<int> st1;
    set<int> st2;

    // 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).
    vector<int> prefix(n + 1, 0);
    vector<int> suffix(n + 1, 0);

    for (int i = 0; i < n; i++) {
        // Calculate the number of elements that
        // are smaller than price[i] using
        // lower_bound() function
        prefix[i] = distance(st1.begin(),
                             st1.lower_bound(price[i]));

        // Insert current price[i] to contribute in
        // the 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
        // lower_bound() function
        suffix[i] = distance(st2.begin(),
                             st2.lower_bound(price[i]));

        // Insert current price[i] to contribute
        // in the next iteration
        st2.insert(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
int main()
{
    vector<int> price = { 1, 2, 8, 5, 3, 4 };
    int k = 2;

    int countOfKSpikes = calculateNumberOfKSpikes(price, k);

    // Function Call
    cout << countOfKSpikes << endl;

    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);
    }
}

Python

def calculate_number_of_k_spikes(price, k):
    n = len(price)

    # Declare ordered sets
    st1 = set()
    st2 = set()

    # Initialize a variable for storing the number of K-spikes
    count_of_k_spikes = 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).
    prefix = [0] * (n + 1)
    suffix = [0] * (n + 1)

    for i in range(n):
        # Calculate the number of elements that
        # are smaller than price[i] using set operations
        prefix[i] = len([x for x in st1 if x < price[i]])

        # Insert current price[i] to contribute in
        # the next iteration
        st1.add(price[i])

    for i in range(n - 1, -1, -1):
        # Calculate the number of elements that
        # are smaller than price[i] using set operations
        suffix[i] = len([x for x in st2 if x < price[i]])

        # Insert current price[i] to contribute
        # in the next iteration
        st2.add(price[i])

    for i in range(n):
        # If prefix and suffix are at least K, then
        # the current element is a K-spike
        if prefix[i] >= k and suffix[i] >= k:
            count_of_k_spikes += 1

    return count_of_k_spikes


# Driver code
if __name__ == "__main__":
    price = [1, 2, 8, 5, 3, 4]
    k = 2

    count_of_k_spikes = calculate_number_of_k_spikes(price, k)

    # Function Call
    print(count_of_k_spikes)
# This Code is Contributed by chinmaya121221

using System;
using System.Collections.Generic;

public class MainClass {
    // Function to calculate the number of spikes in price
    // array
    static int CalculateNumberOfKSpikes(int[] price, int k)
    {
        int n = price.Length;

        // Declare ordered sets
        SortedSet<int> st1 = new SortedSet<int>();
        SortedSet<int> st2 = new SortedSet<int>();

        // 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
            // headSet() function
            prefix[i]
                = st1.GetViewBetween(int.MinValue, price[i])
                      .Count;

            // 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
            // headSet() function
            suffix[i]
                = st2.GetViewBetween(int.MinValue, price[i])
                      .Count;

            // 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
        Console.WriteLine(countOfKSpikes);
    }
}

// This code is contributed by akshitaguprzj3

JavaScript

// Function to calculate the number of K-spikes in the given array
function calculateNumberOfKSpikes(price, k) {
    const n = price.length;

    // Declare sets for prefix and suffix
    const st1 = new Set();
    const st2 = new Set();

    // Initialize a variable for storing the number of K-spikes
    let countOfKSpikes = 0;

    // Arrays to store prefix and suffix counts
    const prefix = new Array(n + 1).fill(0);
    const suffix = new Array(n + 1).fill(0);

    // Calculate prefix counts
    for (let i = 0; i < n; i++) {
        prefix[i] = [...st1].filter(x => x < price[i]).length;

        // Insert current price[i] to contribute in the next iteration
        st1.add(price[i]);
    }

    // Clear sets for suffix calculation
    st1.clear();

    // Calculate suffix counts
    for (let i = n - 1; i >= 0; i--) {
        suffix[i] = [...st2].filter(x => x < price[i]).length;

        // Insert current price[i] to contribute in the next iteration
        st2.add(price[i]);
    }

    // Check for K-spikes
    for (let 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
const price = [1, 2, 8, 5, 3, 4];
const k = 2;

// Function Call
const countOfKSpikes = calculateNumberOfKSpikes(price, k);
console.log(countOfKSpikes);

Output

Time Complexity: O(N*logN)
Auxiliary space: O(N), where N is the size of the array.

Reffered: https://www.geeksforgeeks.org

DSA

Related
Exploring Range Trees
Count the participants defeating maximum individuals in a competition
GCD (Greatest Common Divisor) Practice Problems for Competitive Programming
Euler Totient for Competitive Programming
Find the Neighbours of a Node in a tree

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11