Design
170. Two Sum III - Data structure design
Approach 1 - binary search + sorted array
class TwoSum {
private sortArr: number[];
constructor() {
this.sortArr = new Array();
}
// O(logn)
add(number: number): void {
let l = 0, r = this.sortArr.length;
while (l < r) {
const mid = l + Math.floor((r - l) / 2);
if (this.sortArr[mid] < number) {
l = mid + 1;
} else {
r = mid;
}
}
this.sortArr.splice(l, 0, number);
}
// O(n)
find(value: number): boolean {
let l = 0, r = this.sortArr.length - 1;
while (l < r) {
const sum = this.sortArr[l] + this.sortArr[r];
if (sum === value) return true;
if (sum < value) l++;
else r--;
}
// Check if value is twice a number that appears at least twice
for (let i = 1; i < this.sortArr.length; i++) {
if (this.sortArr[i] === this.sortArr[i - 1] && this.sortArr[i] * 2 === value) {
return true;
}
}
return false;
}
}Approach 2: HashMap / LinkedHashMap
class TwoSum {
private map: Map<number, number>;
constructor() {
this.map = new Map();
}
add(number: number): void {
this.map.set(number, (this.map.get(number) || 0) + 1);
}
find(value: number): boolean {
for (const [k, v] of this.map.entries()) {
const target = value - k;
if (target === k) {
if (this.map.get(target) >= 2) return true;
} else if (this.map.has(target)) {
return true;
}
}
return false;
}
}class TwoSum {
Map<Integer, Integer> map; // number : count
/** Initialize your data structure here. */
public TwoSum() {
map = new HashMap<>();
}
// O(1)
/** Add the number to an internal data structure.. */
public void add(int number) {
map.put(number, map.getOrDefault(number, 0) + 1);
}
// O(n)
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
int curt = it.next();
if ((curt * 2 != value && map.containsKey(value - curt))
|| curt * 2 == value && map.get(curt) >= 2) return true;
}
return false;
}
}
class TwoSum {
LinkedHashMap<Integer, Integer> map; // number : count
/** Initialize your data structure here. */
int min, max;
public TwoSum() {
map = new LinkedHashMap<>();
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
}
/** Add the number to an internal data structure.. */
public void add(int number) {
map.put(number, map.getOrDefault(number, 0) + 1);
min = Math.min(min, number);
max = Math.max(max, number);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
if (value > max * 2 || value < min * 2) return false;
Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
int curt = it.next();
if ((curt * 2 != value && map.containsKey(value - curt))
|| curt * 2 == value && map.get(curt) >= 2) return true;
}
return false;
}
}
/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum obj = new TwoSum();
* obj.add(number);
* boolean param_2 = obj.find(value);
*/class MovingAverage {
Queue<Integer> list;
int capacity;
double sum;
public MovingAverage(int size) {
this.capacity = size;
this.list = new LinkedList<>();
this.sum = 0;
}
public double next(int val) {
list.add(val);
sum += val;
while (list.size() > this.capacity) {
sum -= list.poll();
}
return sum / (double)list.size();
}
}Use a map to store the last time the log is printed.
Map<String, Integer> memo;
/** Initialize your data structure here. */
public Logger() {
memo = new HashMap<>();
}
/** Returns true if the message should be printed in the given timestamp, otherwise returns false.
If this method returns false, the message will not be printed.
The timestamp is in seconds granularity. */
public boolean shouldPrintMessage(int timestamp, String message) {
if (!memo.containsKey(message)) {
memo.put(message, timestamp);
return true;
} else if (memo.containsKey(message) && memo.get(message) <= timestamp - 10) {
memo.put(message, timestamp);
return true;
} else {
return false;
}
}Use a list to store all numbers, use Hashmap <number, it is position> to find the position of each number.
insert: add val to the list and map
remove: check if the val is the last element of the list. If yes, simply remove the last element from list and map. Otherwise, replace val with the last element in the list, and remove the last element.
getRandom:
return list.get(rand.nextInt(list.size()));
List<Integer> list;
Random rand;
Map<Integer, Integer> map;
public RandomizedSet() {
list = new ArrayList<>();
map = new HashMap<>();
rand = new Random();
}
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
list.add(val);
map.put(val, list.size() - 1);
return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
int valpos = map.get(val);
if (valpos != list.size() - 1) {
int lastval = list.get(list.size() - 1);
list.set(valpos, lastval);
map.put(lastval, valpos);
}
map.remove(val);
list.remove(list.size() - 1);
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}Use Map<Integer, Set<Integer>> to store val and corresponding positions. When remove, random pick one from the current val set by using iterator, swap with the last position.
List<Integer> list;
Random rand;
Map<Integer, Set<Integer>> map;
public RandomizedCollection() {
list = new ArrayList<>();
map = new HashMap<>();
rand = new Random();
}
public boolean insert(int val) {
boolean res = !map.containsKey(val);
map.putIfAbsent(val, new HashSet<>());
map.get(val).add(list.size());
list.add(val);
return res;
}
public boolean remove(int val) {
if (!map.containsKey(val)) return false;
int valpos = map.get(val).iterator().next();
map.get(val).remove(valpos);
int lastval = list.get(list.size() - 1);
Set<Integer> lastset = map.get(lastval);
if (valpos != list.size() - 1) {
lastset.remove(list.size() - 1);
lastset.add(valpos);
}
list.set(valpos, lastval);
list.remove(list.size() - 1);
if (map.get(val).isEmpty()) map.remove(val);
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}When new value <= min, add min to the stack then add new value. When pop, check if the popped element equals to min, if yes, pop again.
int min;
Stack<Integer> stack;
public MinStack() {
min = Integer.MAX_VALUE;
stack = new Stack<>();
}
public void push(int x) {
if (x <= min) {
stack.add(min);
min = x;
}
stack.add(x);
}
public void pop() {
int pop = stack.pop();
if (pop == min) {
min = stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}Use an array of size k to store the elements, a start and end to set the boundary and size to maintain the queue size.
int[] arr;
int start, end, size;
public MyCircularQueue(int k) {
arr = new int[k];
start = 0;
end = -1;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull()) return false;
end = (end + 1) % arr.length;
arr[end] = value;
size++;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty()) return false;
start = (start + 1) % arr.length;
size--;
return true;
}
/** Get the front item from the queue. */
public int Front() {
return isEmpty() ? -1 : arr[start];
}
/** Get the last item from the queue. */
public int Rear() {
return isEmpty() ? -1 : arr[end];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return size == 0;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return size == arr.length;
}Clarifications:
For simplicity, are the keys integers only?
For collision resolution, can we use chaining?
Do we have to worry about load factors?
Can we assume inputs are valid or do we have to validate them?
Can we assume this fits memory?
Method: Use a list of buckets to store the node. Each bucket is a linked-list:
int getIndex(int key): get index in the list based on the provide key
ListNode getPrev(int index, int key): get the last node with the right key for insertion or deletion.
Follow-up:
What if there are too many nodes in one bucket? Load factor + rehashing or use Red-Black tree on each node
What if there key is a String? Multiply ASCII value of each character and MOD by 31 to get the index.
class MyHashMap {
ListNode[] list;
int SIZE = 10000;
public MyHashMap() {
list = new ListNode[SIZE];
}
private int getIndex(int key) {
return Integer.hashCode(key) % SIZE;
}
private ListNode getPrev(int index, int key) {
if (list[index] == null) {
list[index] = new ListNode(-1, -1);
return list[index];
}
ListNode prev = list[index];
while (prev.next != null && prev.next.key != key) {
prev = prev.next;
}
return prev;
}
public void put(int key, int value) {
int index = getIndex(key);
ListNode prev = getPrev(index, key);
if (prev.next == null) {
prev.next = new ListNode(key, value);
} else {
prev.next.val = value;
}
}
public int get(int key) {
int index = getIndex(key);
ListNode prev = getPrev(index, key);
if (prev.next == null) {
return -1;
}
return prev.next.val;
}
public void remove(int key) {
int index = getIndex(key);
ListNode prev = getPrev(index, key);
if (prev.next == null) {
return;
}
prev.next = prev.next.next;
}
class ListNode {
int val, key;
ListNode next;
ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
}class LRUCache {
Node head, tail;
int size, capacity;
Map<Integer, Node> map;
public LRUCache(int capacity) {
head = new Node(-1,-1);
tail = new Node(-1,-1);
head.next = tail;
tail.prev = head;
this.size = 0;
this.capacity = capacity;
map = new HashMap<>();
}
public int get(int key) {
if (map.containsKey(key)) {
Node curt = map.get(key);
removeNode(curt);
addToFirst(curt);
return curt.value;
}
return -1;
}
public void put(int key, int value) {
Node curt = null;
if (map.containsKey(key)) {
curt = map.get(key);
curt.value = value;
removeNode(curt);
} else {
curt = new Node(key, value);
if (++size > capacity) {
Node temp = tail.prev;
removeNode(temp);
map.remove(temp.key);
}
}
addToFirst(curt);
map.put(key, curt);
}
private void removeNode(Node curt) {
Node nxt = curt.next;
Node pre = curt.prev;
pre.next = nxt;
nxt.prev = pre;
curt.prev = null;
curt.next = null;
}
private void addToFirst(Node curt) {
Node sec = head.next;
head.next = curt;
curt.prev = head;
curt.next = sec;
sec.prev = curt;
}
class Node {
int key, value;
Node prev, next;
Node(int key, int val) {
this.key = key;
this.value = val;
}
}
}class LFUCache {
Map<Integer, DoublyLinkedList> freqListMap;
Map<Integer, ListNode> keyNodeMap;
int size, capacity, minFrequency;
public LFUCache(int capacity) {
this.freqListMap = new HashMap<>();
this.keyNodeMap = new HashMap<>();
this.size = 0;
this.capacity = capacity;
this.minFrequency = 0;
}
public int get(int key) {
ListNode curt = keyNodeMap.get(key);
if (curt == null) {
return -1;
}
updateNode(curt);
return curt.val;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (keyNodeMap.containsKey(key)) {
ListNode curt = keyNodeMap.get(key);
curt.val = value;
updateNode(curt);
} else {
size++;
if (size > capacity) {
DoublyLinkedList minList = freqListMap.get(minFrequency);
ListNode deleteNode = minList.popLast();
keyNodeMap.remove(deleteNode.key);
size--;
}
minFrequency = 1;
ListNode curt = new ListNode(value);
curt.key = key;
DoublyLinkedList ddl = freqListMap.getOrDefault(
curt.freq, new DoublyLinkedList());
ddl.addToFirst(curt);
keyNodeMap.put(key, curt);
freqListMap.put(curt.freq, ddl);
}
}
private void updateNode(ListNode curt) {
int curtFeq = curt.freq;
DoublyLinkedList ddl = freqListMap.get(curtFeq);
ddl.popNode(curt);
if (curtFeq == minFrequency && ddl.emptyList()) {
minFrequency++;
}
curt.freq += 1;
DoublyLinkedList nextDDL = freqListMap.getOrDefault(
curtFeq + 1, new DoublyLinkedList());
nextDDL.addToFirst(curt);
freqListMap.put(curtFeq + 1, nextDDL);
}
class DoublyLinkedList {
ListNode head, tail;
DoublyLinkedList() {
this.head = new ListNode(-1);
this.tail = new ListNode(-1);
head.next = tail;
tail.prev = head;
}
public void addToFirst(ListNode curtNode) {
ListNode next = head.next;
curtNode.next = next;
next.prev = curtNode;
head.next = curtNode;
curtNode.prev = head;
}
public ListNode popNode(ListNode node) {
ListNode next = node.next;
node.prev.next = next;
next.prev = node.prev;
node.prev = null;
node.next = null;
return node;
}
public ListNode popLast() {
ListNode last = tail.prev;
return popNode(last);
}
private boolean emptyList() {
return head.next == tail && tail.prev == head;
}
}
class ListNode {
ListNode prev, next;
int freq;
int val;
int key;
ListNode(int val) {
this.val = val;
this.freq = 1;
}
}
}Solution1: two stacks
Solution2: Use a LinkedList and TreeMap to store value.
class MaxStack {
Stack<Integer> stack;
Stack<Integer> maxStack;
public MaxStack() {
stack = new Stack();
maxStack = new Stack();
}
public void push(int x) {
int max = maxStack.isEmpty() ? x : maxStack.peek();
maxStack.push(max > x ? max : x);
stack.push(x);
}
public int pop() {
maxStack.pop();
return stack.pop();
}
public int top() {
return stack.peek();
}
public int peekMax() {
return maxStack.peek();
}
public int popMax() {
int max = peekMax();
Stack<Integer> buffer = new Stack();
while (top() != max) buffer.push(pop());
pop();
while (!buffer.isEmpty()) push(buffer.pop());
return max;
}
}This is similar to LFU. Each bucket is has a pre bucket and a next buck, also has a keySet to store all keys in the frequency, and the frequency itself. Build two maps:
Key: Count Value: Bucket
Key: String Key Value: Count
// maintain a doubly linked list of Buckets
private Bucket head;
private Bucket tail;
// for accessing a specific Bucket among the Bucket list in O(1) time
private Map<Integer, Bucket> countBucketMap;
// keep track of count of keys
private Map<String, Integer> keyCountMap;
// each Bucket contains all the keys with the same count
private class Bucket {
int count;
Set<String> keySet;
Bucket next;
Bucket pre;
public Bucket(int cnt) {
count = cnt;
keySet = new HashSet<>();
}
}
/** Initialize your data structure here. */
public AllOne() {
head = new Bucket(Integer.MIN_VALUE);
tail = new Bucket(Integer.MAX_VALUE);
head.next = tail;
tail.pre = head;
countBucketMap = new HashMap<>();
keyCountMap = new HashMap<>();
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
public void inc(String key) {
if (keyCountMap.containsKey(key)) {
changeKey(key, 1);
return;
}
keyCountMap.put(key, 1);
if (head.next.count != 1) {
addBucketAfter(new Bucket(1), head);
}
head.next.keySet.add(key);
countBucketMap.put(1, head.next);
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
if (keyCountMap.containsKey(key)) {
int count = keyCountMap.get(key);
if (count == 1) {
removeKeyFromBucket(countBucketMap.get(1), key);
keyCountMap.remove(key);
} else {
changeKey(key, -1);
}
}
}
/** Returns one of the keys with maximal value. */
public String getMaxKey() {
return tail.pre == head ? "" : (String) tail.pre.keySet.iterator().next();
}
/** Returns one of the keys with Minimal value. */
public String getMinKey() {
return head.next == tail ? "" : (String) head.next.keySet.iterator().next();
}
// helper function to make change on given key according to offset
private void changeKey(String key, int offset) {
int count = keyCountMap.get(key);
keyCountMap.put(key, count + offset);
Bucket curBucket = countBucketMap.get(count);
Bucket newBucket;
if (countBucketMap.containsKey(count + offset)) {
// target Bucket already exists
newBucket = countBucketMap.get(count + offset);
} else {
// add new Bucket
newBucket = new Bucket(count + offset);
countBucketMap.put(count + offset, newBucket);
addBucketAfter(newBucket, offset == 1 ? curBucket : curBucket.pre);
}
newBucket.keySet.add(key);
removeKeyFromBucket(curBucket, key);
}
private void removeKeyFromBucket(Bucket bucket, String key) {
bucket.keySet.remove(key);
if (bucket.keySet.size() == 0) {
removeBucketFromList(bucket);
countBucketMap.remove(bucket.count);
}
}
private void removeBucketFromList(Bucket bucket) {
bucket.pre.next = bucket.next;
bucket.next.pre = bucket.pre;
bucket.next = null;
bucket.pre = null;
}
// add newBucket after preBucket
private void addBucketAfter(Bucket newBucket, Bucket preBucket) {
newBucket.pre = preBucket;
newBucket.next = preBucket.next;
preBucket.next.pre = newBucket;
preBucket.next = newBucket;
}BinarySearch version
Map<String, List<Pair>> map;
public TimeMap() {
map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(new Pair(timestamp, value));
}
public String get(String key, int timestamp) {
List<Pair> list = map.get(key);
if (list == null || list.get(0).timestamp > timestamp) return "";
if (list.get(list.size() - 1).timestamp < timestamp) return list.get(list.size() - 1).value;
return binarySearch(list, timestamp);
}
public String binarySearch(List<Pair> list, int timestamp) {
int left=0, right = list.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
int ts = list.get(mid).timestamp;
if (timestamp == ts) {
return list.get(mid).value;
} else if (timestamp > ts) {
if (mid + 1 < list.size() && timestamp < list.get(mid+1).timestamp) {
return list.get(mid).value;
} else {
left = mid + 1;
}
} else {
right = mid -1;
}
}
return "";
}
class Pair {
int timestamp;
String value;
Pair(int t, String v) {
this.timestamp = t;
this.value = v;
}
}TreeMap version
Map<String,TreeMap<Integer, String>> map;
public TimeMap() {
map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
map.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
}
public String get(String key, int timestamp) {
if(map.containsKey(key)){
TreeMap<Integer, String> m = map.get(key);
Integer val = m.floorKey(timestamp);
if(val!=null)
return m.get(val);
}
return "";
}Store all seats in a TreeMap, loop over it to detect the largest gap.
class ExamRoom {
TreeSet<Integer> set;
int N;
public ExamRoom(int N) {
set = new TreeSet<>();
this.N = N;
}
public int seat() {
if (set.isEmpty()) {
set.add(0);
return 0;
}
int maxInterval = set.first();
int pre = set.first(), seat = 0;
for (int curt : set) {
if ((curt - pre) / 2 > maxInterval) {
maxInterval = (curt - pre) / 2;
seat = (curt + pre) / 2;
}
pre = curt;
}
if (N - pre - 1 > maxInterval) {
seat = N - 1;
}
set.add(seat);
return seat;
}
public void leave(int p) {
set.remove(p);
}
}class BrowserHistory {
/**
4. linkedin.com
3. youtube.com
2. facebook.com
1. google.com
*/
public:
vector<string> list;
int index;
BrowserHistory(string homepage) {
list.push_back(homepage);
index = 0;
}
void visit(string url) {
list.resize(index + 1);
list.push_back(url);
index++;
}
string back(int steps) {
index = max(0, index - steps);
return list[index];
}
string forward(int steps) {
index = min((int)list.size() - 1, index + steps);
return list[index];
}
};
/**
* Your BrowserHistory object will be instantiated and called as such:
* BrowserHistory* obj = new BrowserHistory(homepage);
* obj->visit(url);
* string param_2 = obj->back(steps);
* string param_3 = obj->forward(steps);
*/import java.util.*;
class Solution {
class Transaction {
String raw;
String name;
int time;
int amount;
String city;
Transaction(String s) {
raw = s;
String[] parts = s.split(",");
name = parts[0];
time = Integer.parseInt(parts[1]);
amount = Integer.parseInt(parts[2]);
city = parts[3];
}
}
public List<String> invalidTransactions(String[] transactions) {
int n = transactions.length;
Transaction[] txns = new Transaction[n];
boolean[] invalid = new boolean[n];
// Parse all transactions and group them by name
Map<String, List<Integer>> nameToIndices = new HashMap<>();
for (int i = 0; i < n; i++) {
txns[i] = new Transaction(transactions[i]);
nameToIndices
.computeIfAbsent(txns[i].name, k -> new ArrayList<>())
.add(i);
// Rule 1: amount > 1000
if (txns[i].amount > 1000) {
invalid[i] = true;
}
}
// Rule 2: check conflicting transactions by name
for (Map.Entry<String, List<Integer>> entry : nameToIndices.entrySet()) {
List<Integer> indices = entry.getValue();
for (int i : indices) {
Transaction t1 = txns[i];
for (int j : indices) {
if (i == j) continue;
Transaction t2 = txns[j];
if (!t1.city.equals(t2.city) && Math.abs(t1.time - t2.time) <= 60) {
invalid[i] = true;
break;
}
}
}
}
List<String> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (invalid[i]) {
result.add(txns[i].raw);
}
}
return result;
}
}
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
class SQL {
map<string, int> tableMap;
map<string, int> columnCount;
map<string, int> nextRowId;
vector<vector<pair<int, vector<string>>>> tables;
public:
SQL(vector<string>& names, vector<int>& columns) {
int n = names.size();
tables.resize(n);
for (int i = 0; i < n; ++i) {
tableMap[names[i]] = i;
columnCount[names[i]] = columns[i];
nextRowId[names[i]] = 1;
}
}
bool ins(string name, vector<string> row) {
if (tableMap.find(name) == tableMap.end()) return false;
if (row.size() != columnCount[name]) return false;
int tableId = tableMap[name];
int rowId = nextRowId[name]++;
tables[tableId].push_back({rowId, row});
return true;
}
void rmv(string name, int rowId) {
if (tableMap.find(name) == tableMap.end()) return;
int tableId = tableMap[name];
auto& table = tables[tableId];
for (auto it = table.begin(); it != table.end(); ++it) {
if (it->first == rowId) {
table.erase(it);
break;
}
}
}
string sel(string name, int rowId, int columnId) {
if (tableMap.find(name) == tableMap.end()) return "<null>";
int tableId = tableMap[name];
auto& table = tables[tableId];
for (auto& [rid, row] : table) {
if (rid == rowId) {
if (columnId < 1 || columnId > row.size()) return "<null>";
return row[columnId - 1];
}
}
return "<null>";
}
vector<string> exp(string name) {
if (tableMap.find(name) == tableMap.end()) return {};
int tableId = tableMap[name];
auto& table = tables[tableId];
vector<string> result;
for (auto& [rowId, row] : table) {
vector<string> outputRow;
outputRow.push_back(to_string(rowId));
outputRow.insert(outputRow.end(), row.begin(), row.end());
result.push_back(joinWithComma(outputRow));
}
return result;
}
private:
string joinWithComma(const vector<string>& vec) {
ostringstream oss;
for (size_t i = 0; i < vec.size(); ++i) {
if (i > 0) oss << ",";
oss << vec[i];
}
return oss.str();
}
};
Mine Sweeper
import java.io.*;
import java.util.*;
class Solution {
public static void main(String[] args) {
Minesweeper minesweeper = new Minesweeper(5, 5, 4);
minesweeper.print();
System.out.println("\nClick (0, 0)");
minesweeper.click(0, 0);
minesweeper.print();
System.out.println("\nClick (0, 4)");
minesweeper.click(0, 4);
minesweeper.print();
System.out.println("\nClick (2, 0)");
minesweeper.click(2, 0);
minesweeper.print();
}
static class Minesweeper {
String[][] grid; // What user sees
String[][] mineGrid; // Actual state with mine counts
int rows, cols;
int[][] dirs = {
{1, 0}, {0, 1}, {-1, 0}, {0, -1},
{1, 1}, {-1, 1}, {1, -1}, {-1, -1}
};
Minesweeper(int rows, int cols, int mineCount) {
this.rows = rows;
this.cols = cols;
this.grid = new String[rows][cols];
this.mineGrid = new String[rows][cols];
for (String[] r : grid) Arrays.fill(r, "-");
for (String[] r : mineGrid) Arrays.fill(r, "-");
generateMines(mineCount);
preProcess();
}
public void click(int x, int y) {
if (!inbound(x, y) || !grid[x][y].equals("-")) return;
if (mineGrid[x][y].equals("X")) {
System.out.println("Hit Mine, Game Over");
// Reveal all mines
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (mineGrid[i][j].equals("X")) {
grid[i][j] = "X";
}
}
}
return;
}
// DFS to reveal all connected 0-cells and borders
dfsReveal(x, y);
}
private void dfsReveal(int x, int y) {
if (!inbound(x, y) || !grid[x][y].equals("-")) return;
String val = mineGrid[x][y];
grid[x][y] = val;
if (val.equals("0")) {
for (int[] d : dirs) {
dfsReveal(x + d[0], y + d[1]);
}
}
}
public void print() {
System.out.println("User Grid:");
for (String[] row : grid) {
System.out.println(Arrays.toString(row));
}
System.out.println("Mine Grid:");
for (String[] row : mineGrid) {
System.out.println(Arrays.toString(row));
}
}
private void generateMines(int count) {
Random rand = new Random();
int placed = 0;
while (placed < count) {
int x = rand.nextInt(rows);
int y = rand.nextInt(cols);
if (mineGrid[x][y].equals("-")) {
mineGrid[x][y] = "X";
placed++;
}
}
}
private void preProcess() {
for (int x = 0; x < rows; x++) {
for (int y = 0; y < cols; y++) {
if (mineGrid[x][y].equals("X")) continue;
int count = 0;
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (inbound(nx, ny) && mineGrid[nx][ny].equals("X")) {
count++;
}
}
mineGrid[x][y] = String.valueOf(count);
}
}
}
private boolean inbound(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
}
}
class Excel {
public:
int table[27][27]; // fixed-size table for up to 26 columns (A-Z) and 27 rows
map<pair<int, int>, vector<pair<int, int>>> graph;
Excel(int height, char width) {
memset(table, 0, sizeof(table));
}
void set(int row, char column, int val) {
int x = row, y = column - 'A';
table[x][y] = val;
graph[{x, y}] = {}; // clear formula dependencies
}
int get(int row, char column) {
int x = row, y = column - 'A';
map<pair<int, int>, int> memo;
return dfs(x, y, memo);
}
int sum(int row, char column, vector<string> numbers) {
int x = row, y = column - 'A';
graph[{x, y}].clear(); // reset existing formula
table[x][y] = 0; // reset value
for (const string& num : numbers) {
vector<int> n = split(num); // returns [col1, row1] or [col1, row1, col2, row2]
if (n.size() == 2) {
graph[{x, y}].emplace_back(n[1], n[0]);
} else {
for (int i = n[1]; i <= n[3]; ++i) {
for (int j = n[0]; j <= n[2]; ++j) {
graph[{x, y}].emplace_back(i, j);
}
}
}
}
map<pair<int, int>, int> memo;
return dfs(x, y, memo);
}
private:
int dfs(int i, int j, map<pair<int, int>, int>& memo) {
pair<int, int> key = {i, j};
if (memo.count(key)) return memo[key];
int ans = table[i][j];
for (const auto& [ni, nj] : graph[key]) {
ans += dfs(ni, nj, memo);
}
memo[key] = ans;
return ans;
}
vector<int> split(const string& s) {
vector<int> res;
string number;
for (char c : s) {
if (isalpha(c)) {
if (!number.empty()) {
res.push_back(stoi(number));
number.clear();
}
res.push_back(c - 'A'); // Convert letter to 0-based column index
} else if (isdigit(c)) {
number += c;
} else if (c == ':' && !number.empty()) {
res.push_back(stoi(number));
number.clear();
}
}
if (!number.empty()) {
res.push_back(stoi(number));
}
return res;
}
};
Last updated
Was this helpful?