Get this book -> Problems on Array: For Interviews and Competitive Programming

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:

- Problem Statement
- Naive approach for new Data Structure
- 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

- insert element
- define function
`product_of_k_ele()`

- calculate product of last
`k`

elements by multiplying last k elements using linear traverse - return calculated product

- calculate product of last

#### 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 `k`

from 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

- insert
`a`

in ds then`product = a`

,`container = [a]`

- insert
`b`

in ds then`product = a*b`

,`container = [(a b)]`

- insert
`c`

in ds then`product = (a*b*c)/a= b*c`

,`container = [a (b c)]`

- 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

- insert element
- define function
`product_of_k_ele()`

- return product of last
`k`

elements

- return product of last

### 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.