In this problem, We have to design a data structure that supports Insert, Delete, and GetRandom in average O(1) time.
OR
Design a data structure that supports insert, delete, and getRandom in constant time O(1).
insert(value): Inserts an item value to the set if it’s not present.
remove(value): Removes an item value from the set if present.
getRandom(): Returns a random element from current set of elements. Each element must have the same probability of being returned.
In this tutorial, I am going to discuss a very famous interview problem. How to count the number of islands.
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
You may assume all four edges of the grid are surrounded by water.
How to find all duplicates in an array without using extra space?
Given an array of integers, the integers are in the range of 1 ≤ a[i] ≤ n (n = size of array). In this Array, some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
We have to solve this problem without using extra space and in O(n) time complexity.
For Example:
Input: [4, 3, 2, 7, 8, 2, 3, 1]
Output: [2, 3]