Design a Number Container System
Problem Statement
Aapko ek number container system design karna hai jo yeh kar sake:
Diye gaye index par ek number daalna ya replace karna.
System mein diye gaye number ke liye sabse chhota index return karna.
Aapko
NumberContainersclass implement karna hai:Methods
NumberContainers(): Number container system ko initialize karta hai.
void change(int index, int number): Diye gaye index par number daalta hai. Agar us index par pehle se koi number hai, toh usse replace karta hai.
int find(int number): Diye gaye number ke liye sabse chhota index return karta hai, ya agar aisa koi index nahi hai toh -1 return karta hai.
Example
plaintextInput: ["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"] [[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]] Output: [null, -1, null, null, null, null, 1, null, 2]Explanation:
NumberContainers nc = new NumberContainers();– Number container system ko initialize karta hai.nc.find(10);– 10 number ke liye koi index nahi hai, isliye -1 return karta hai.nc.change(2, 10);– Index 2 par number 10 daalta hai.nc.change(1, 10);– Index 1 par number 10 daalta hai.nc.change(3, 10);– Index 3 par number 10 daalta hai.nc.change(5, 10);– Index 5 par number 10 daalta hai.nc.find(10);– Number 10 index 1, 2, 3, aur 5 par hai. Sabse chhota index 1 hai, isliye 1 return karta hai.nc.change(1, 20);– Index 1 par number 20 daalta hai. Pehle yahan 10 tha, jise replace karke 20 kar diya gaya.nc.find(10);– Number 10 ab index 2, 3, aur 5 par hai. Sabse chhota index 2 hai, isliye 2 return karta hai.
Constraints
1≤index, number≤1091 \leq \text{index, number} \leq 10^9
Kul milakar
changeaurfindpar adhik tam 105 calls ki ja sakti hain.
Design a Number Container System
Ye problem aapko efficiently indices aur values ko track karne ki zarurat hai taaki aap do cheezein kar sako:
Update karna ek index ko ek naye number ke saath: Jab aap change(index, number) call karte ho, toh system mein kisi specific index ko naye number ke saath update karna padta hai.
Kisi specific number ko store karne wale sabse chhote index ko find karna: Jab aap find(number) call karte ho, toh system mein sabse chhota index return karna padta hai jo ki uss number ko store karta hai.Steps:
HashMaps:
index_val: Yeh ek HashMap hai jo har index par stored number ko track karta hai. Matlab, index par konsa number hai, yeh store karega.
res: Yeh ek HashMap hai jo har number ko uske sabse chhote indices ke MinHeap se map karta hai. Matlab, number ke corresponding indices ko efficiently track karta hai.
Efficient Updates:
Jab ek index change hota hai, humein purane value ko uske heap se nikalna padta hai.
Naya index uske naye number ke heap mein add karna hota hai.
Time Complexity:
change(index, number) → O(log N):
Jab hum
changefunction call karte hain aur ek number ko heap mein insert karte hain, toh yeh operation O(log N) mein hota hai.Yeh heap insert operation ki wajah se hota hai, jo ki efficiently index ko MinHeap mein add karta hai.
find(number) → O(log N):
Jab hum
findfunction call karte hain, toh hume heap mein cleanup karna padta hai taaki sabse chhota index mil sake.Yeh operation bhi O(log N) mein hota hai kyunki heap cleanup ya extraction operation O(log N) mein hota hai.
Space Complexity:
O(N):
Space complexity O(N) hoti hai kyunki hume indices ko hash maps aur heaps mein store karna padta hai.
HashMap
index_valaurresdono ki space complexity O(N) hoti hai kyunki yeh N indices aur corresponding values ko store karte hain.
Solution
class MinHeap {
constructor() {
this.heap = [];
}
// MinHeap mein value add karna
push(val) {
this.heap.push(val);
this._bubbleUp(); // Bubble up operation perform karna
}
// MinHeap se minimum value nikalna
pop() {
if (this.heap.length === 0) return -1; // Agar heap empty hai toh -1 return karo
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this._heapifyDown(); // Heapify down operation perform karna
}
return min; // Min value return karo
}
// MinHeap ke top value dekhna
peek() {
return this.heap.length ? this.heap[0] : -1; // Agar heap empty hai toh -1 return karo
}
// Bubble up operation heap structure maintain karne ke liye
_bubbleUp() {
let idx = this.heap.length - 1;
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
if (this.heap[parentIdx] <= this.heap[idx]) break; // Agar parent value chhoti hai toh break karo
[this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]]; // Swap karo
idx = parentIdx;
}
}
// Heapify down operation heap structure maintain karne ke liye
_heapifyDown() {
let idx = 0;
while (true) {
let left = 2 * idx + 1,
right = 2 * idx + 2,
smallest = idx;
if (left < this.heap.length && this.heap[left] < this.heap[smallest]) smallest = left; // Left child chhota hai toh smallest update karo
Purpose: Yeh class ek MinHeap data structure implement karti hai, jo minimum element ko efficiently maintain karti hai.
Methods:
push(val): Yeh method heap mein ek naya value add karta hai aur bubble up operation ke through sahi position par place karta hai.pop(): Yeh method heap se minimum value nikalta hai aur heap structure ko maintain karta hai.peek(): Yeh method heap ka top (minimum) value return karta hai bina usse remove kiye._bubbleUp(): Yeh private method nayi added value ko upar move karta hai jab tak sahi position na mil jaye._heapifyDown(): Yeh private method top value ko neeche move karta hai jab tak sahi position na mil jaye.
NumberContainers Class:
Purpose: Yeh class number container system ko implement karti hai jo indices aur values ko efficiently track karti hai.
Attributes:
indexMap: Yeh map har index par stored number ko track karta hai.numberMap: Yeh map har number ko uske indices ke MinHeap se map karta hai.
Methods:
change(index, number):Agar index pehle se kisi number se filled hai, toh us number ko uske heap se remove karte hain.
Fir, naye number ke corresponding heap mein index ko add karte hain.
find(number):Yeh method number ke corresponding MinHeap se sabse chhota index find karta hai.
Agar aisa index nahi hai toh -1 return karta hai.
Solution
#include <unordered_map>
#include <queue>
using namespace std;
class NumberContainers {
public:
// res: har number ke liye MinHeap (priority_queue) of indices store karta hai
unordered_map<int, priority_queue<int, vector<int>, greater<int>>> res;
// index_val: har index par stored number track karta hai
unordered_map<int, int> index_val;
// Diye gaye index par number change ya insert karta hai
void change(int index, int number) {
if (index_val.count(index)) { // Agar index pehle se exist karta hai
int prevNum = index_val[index];
if (prevNum == number) return; // Agar pehle ka number aur naya number same hai toh return karo
res[prevNum].push(INT_MAX); // Lazy deletion: purane number ko mark karne ke liye
}
res[number].push(index); // Naye number ke corresponding index ko MinHeap mein push karo
index_val[index] = number; // Index par naye number ko map karo
}
// Diye gaye number ke liye sabse chhota index return karta hai
int find(int number) {
// MinHeap cleanup: Agar MinHeap top index ka number match nahi karta toh pop karo
while (!res[number].empty() && index_val[res[number].top()] != number) {
res[number].pop();
}
// Agar MinHeap empty hai toh -1 return karo, nahi toh top index return karo
return res[number].empty() ? -1 : res[number].top();
}
};
Classes and Purpose:
NumberContainers class is designed to manage a system where numbers are stored at specific indices. It uses HashMaps and MinHeap for efficiency.
Data Structures:
index_val: Yeh unordered_map har index par stored number ko track karta hai. Matlab, yeh map karta hai ki kaunse index par kaunsa number hai.
res: Yeh unordered_map har number ke corresponding MinHeap (priority_queue) of indices ko store karta hai. Matlab, yeh map karta hai ki kaunse number ke saath kaunse indices associated hain, aur MinHeap ke through minimum index ko maintain karta hai.
Methods:
change(index, number):
Agar given index pehle se kisi number se filled hai, toh pehle us number ko uske corresponding heap se remove karta hai (lazy deletion ka use karke).
Fir, naye number ke corresponding index ko MinHeap mein add karta hai.
Last mein, index ko naye number ke saath update karta hai
index_valmap mein.
find(number):
Given number ke corresponding MinHeap se sabse chhota index find karta hai.
Agar MinHeap mein top index ka number match nahi karta toh, top ko remove kar deta hai.
Agar MinHeap empty hai toh -1 return karta hai, nahi toh top index return karta hai.
