In this article, we have presented 2 designs for Data Structure with insert and product of last K elements operations. Both operations can be done in constant time O(1).

Table of contents:

1. Problem Statement
2. Naive approach for new Data Structure
3. Optimal solution for new Data Structure

To practice more such similar problems of designing Data Structures, go through this article.

Prerequisite: Prefix Sum Array

Let us get started with Data Structure with insert and product of last K elements operations.

Problem Statement

We have to design a Data Structure that support the following operations:

• Insert: to insert a new element E into the Data Structure
• ProductK: to return the product of the last K elements inserted

The given input list be [1, 2, 3, 4, 5, 6], and value for k is 3

Therefore the product for last k=3 elements is: result = 4 * 5 * 6 = 120

Naive approach for new Data Structure

In this approach, we will use simple vector for storing list. The structure will be like this:

class data_structure{
  vector<double> a;  
  int k;
}

We will create two functions insert(x) to add elements and product_of_k_ele() to return of last k elements

insert(int x)

• this will just add elements in vector
• time complexity: O(1)

product_of_k_ele()

• this will calculate the product of last k elements simply by traversing last k elements.
• time complexity: O(K)

Pseudo code

• declare empty container and two variables for storing value k.
• define function insert(x)
  • insert element x in last
• define function product_of_k_ele()
  • calculate product of last k elements by multiplying last k elements using linear traverse
  • return calculated product

Code

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

class data_structure{
  vector<double> a;  
  int k;

  public:
  // constructor for declaring variable k
  data_structure(int x){
    k=x;
  }

  // function for inserting elements in data structure
  void insert(double x){
    a.push_back(x);
  }

  // function for fetching product of last k elements
  double product_of_k_ele(){
    double product=1;
    for(int i=a.size()-k; i<a.size(); i++) product*=a[i];
    return product;
  }
};

void solve()
{
  // n = no of element data structure, k number of element from end
  int n, k; cin>>n>>k;
  data_structure ds(k);
  int temp;
  for(int i=1; i<=n; i++){
    cin>>temp;
    // inserting n elements in data structure
    ds.insert((double) temp);
  }
  cout<<ds.product_of_k_ele()<<endl;
}

int main() {
  solve();
  return 0;
}

Optimal solution for new Data Structure

The technique that is used here is sliding window technique in which we will take window of size kfrom end of list and return product of all elements within that sliding window

Here we have used vector to make or container flexible and well indexed

• as our AIM is to get product of last k elements, we have created two functions insert(x) to add element x to our data_structure and calculate the product of k elements, product_of_k_ele() to just return product of last k elements
• insert(x) function we will first we will insert element in our container and till the size of vector is less then k we will just multiply product with element that we are inserting
• and when the container size is equal to k then our sliding window of size k can be formed and the product of elements in sliding window will get stored in product variable
• Now when the size of our container is k and we add a new element then we need to shift our sliding window to right by 1 as we want the product of last k elements or product of the last sliding window of size k. We need to only visualize sliding window and for calculating product of last sliding window we can just multiply newly inserted element with product and for removing contribution of last element we can just divide product with the element which we have to remove from sliding window

Ex: let k=2(size of sliding window) or our data structure
and we want to insert 4 elements

1. insert a in ds then product = a, container = [a]
2. insert b in ds then product = a*b, container = [(a b)]
3. insert c in ds then product = (a*b*c)/a= b*c, container = [a (b c)]
4. insert d in ds then product = (b*c*d)/b= c*d, container = [a b (c d)]

our result will be c*d

Note: () in container is representing sliding window

by this we can clearly see that for maintaining the product of last k element using this technique we can easily calculate product in O(1) at the time of insertion.

The structure of our new Data Structure will be:

class data_structure {
  vector<double> a;
  int k;
  double product;
}

Example:

• let the given array be [1, 2, 3, 4, 5, 6] of size = 6 and let the value of k = 3.
• as k = 3 then the size of sliding window will also be 3
• now we will insert each element one by one and multiply product with those number till the vector size is less then k
• when vector size will be k then our first sliding window of size k will be [1, 2, 3] and the product of elements will be stored in product variables. therefore product = 1*2*3
• then of we insert new element then our new sliding window will be [2, 3, 4] then in product 1*2*3*4 will get stored, for removing contribution of element before the first element of sliding window we will divide product with that element
• therefore product will be (1*2*3*4)/1 = 2*3*4
• when we add next element that is 5
  then new sliding window = [3, 4, 5] and product will be 2*3*4*5
  for removing contribution of element before first element of sliding window we will divide product with that element
• therefore product = (2*3*4*5)/2 = 3*4*5
• after inserting all elements we will get our last sliding window as [4, 5, 6] and product = 4*5*6
• product of last k element will get stored in product and we can fetch that using product_of_k_ele() function
• we only have to visualize sliding window and focus on product variable in which we are storing product elements of last sliding window of size k in our vector of container

insert(int x)

• this will add element x in our data structure
• time complexity: O(1)
• also it will calculate product of k element at the time of insertion only which will take O(1) time

product_of_k_ele()

• this function will return product of last k element
• time complexity: O(1)

Pseudocode

• declare empty container and two variables for storing product of k elements and value k.
• define function insert(x)
  • insert element x in last
  • calculating product of last k elements and update variable for product of k element variable
• define function product_of_k_ele()
  • return product of last k elements

Code

// Part of iq.opengenus.org
#include<iostream>
#include<vector>
using namespace std;

class data_structure{
  vector<double> a;
  int k;
  double product;

  public:
  // constructor for declaring variable k
  data_structure(int x){
    k=x;
  }

  // function for inserting elements in data structure
  void insert(double x){
    a.push_back(x);
    if(a.size()==1) product=a[0];
    else if(a.size()>k) product/=a[a.size()-k-1], product*=x;
    else product*=x;
  }

  // function for fetching product of last k elements
  double product_of_k_ele(){
    return product;
  }
};

void solve()
{
  // n = no of element data structure, k number of element from end
  int n, k; cin>>n>>k;
  data_structure ds(k);
  int temp;
  for(int i=1; i<=n; i++){
    cin>>temp;
    // inserting n elements in data structure
    ds.insert((double) temp);
  }
  cout<<ds.product_of_k_ele()<<endl;
}
int main() {
  solve();
  return 0;
}

Input

6 3
1
2
3
4
5
6

Output

120

With this article at OpenGenus, you must have the complete idea of Data Structure with insert and product of last K elements operations.