🚀 Mastering Array and Hashing Problems: 10 Essential Challenges
Are you ready to level up your algorithmic and data structure skills? Dive into these thrilling problems that encompass a variety of techniques and concepts related to arrays and hashing. Let's embark on this exciting journey of problem-solving prowess!
1. Contains Duplicate
Overview: Determine if there are any duplicate elements in the array.
Techniques: Hashing (HashSet) for efficient duplicate checking.
2. Valid Anagram
Overview: Check if two strings are anagrams of each other.
Techniques: Hashing (HashMap) and frequency counter technique for character count comparison.
3. 2 Sum
Overview: Find two numbers that sum up to a specific target.
Techniques: Hashing (HashMap) for efficient element storage and lookup.
4. Group Anagram
Overview: Group anagrams together from a list of strings.
Techniques: Hashing (HashMap) and sorting for efficient grouping.
5. Longest Consecutive Sequence
Overview: Find the length of the longest consecutive element sequence.
Techniques: Hashing (HashSet) for efficient consecutive element checking.
6. Maximum Subarray (Kaden's Algorithm)
Overview: Find the contiguous subarray with the largest sum.
Techniques: Kaden's Algorithm, dynamic programming, prefix & suffix sum techniques for linear time complexity.
7. Next Permutation
Overview: Find the lexicographically next greater permutation of numbers.
Techniques: Swapping and reversing for efficient permutation finding.
8. Maximum Product Subarray
Overview: Find the contiguous subarray with the largest product.
Techniques: Similar approach to Kadane's algorithm, adapted for product computation.
9. Majority Element (Moor's Voting Algorithm)
Overview: Find the majority element in an array.
Techniques: Moor's Voting Algorithm for linear time and constant space complexity.
10. Trapping Rain Water
Overview: Calculate trapped rainwater between bars.
Techniques: Two-pointer technique and variable caching for optimized time and space complexity.
These challenges encompass a wide range of techniques such as hashing, frequency counting, two-pointer concept, sliding window, prefix & suffix sum, swapping, reversing, Moor's voting algorithm, and caching. Mastering them will establish a robust foundation for efficiently tackling array and hashing-related questions.
Get ready to conquer these challenges and elevate your problem-solving skills to new heights!
1. Contains Duplicate (leetcode link)
/**
Intuition:
- we will use a HashSet(since it contain only unique value and we can access
element in 0(1) time)
- we can use ArrayList too but it will increase Time complexity to O(n^2) because
searching in Array takes O(n) time
- while iterating through the element we will check HashSet to see if the element exists
in HashSet means we have duplicate
so we will return true while reaching the end of the array if
we didn't find a duplicate then returned false'
**/
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> hs = new HashSet();
for(int e : nums)
{
if(hs.contains(e))
{
return true;
}
hs.add(e);
}
return false;
}
}
//Time -O(n) because we are iterating each element only once
adding and searching elements to hashSet is almost constant O(1)
//Space - O(n) because we are using extra data-structure hashSet
2. Valid Anagram (leetcode link)
/**
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word
or phrase, typically using all the original letters exactly once.
Intuition:
- iterate the first and get the frequency array by adding
number of times we have seen a particular character in the string
( frequency array will be of size 26 representing 0 index as 'a' and 25 index as 'z')
- iterate the second string and reduce the frequency
- iterate from a to z frequency array if we find any frequency
count other than 0 then return false else true
**/
class Solution {
public boolean isAnagram(String s, String t) {
//frequency array
int[] fre = new int[26];
if(s.length() != t.length())
{
return false;
}
for(int i = 0; i < s.length(); i++)
{
int index = s.charAt(i) - 'a';
fre[index]++;
}
for(int i = 0; i < t.length(); i++)
{
int index = t.charAt(i) - 'a';
fre[index]--;
//new char found in 2nd string which doesn't exists in 1st string
if(fre[index] < 0)
{
return false;
}
}
//check if any element exists in 1st string but not in second
for(int i = 0; i < 26; i++)
{
if(fre[i] != 0)
{
return false;
}
}
return true;
}
}
/**
-Time Complexity: O(n) consider length of s and t as n
then we iterate through s once and t also once and
frequency array of 26 O(n+n+26) -> O(2n + 26) -> O(n)
-Space Complexity: O(1) Though we used an extra frequency
array it's of fixed size 26 so it's considered as a constant.
**/
3. 2 Sum (leetcode link)
/**
Given an array of integer nums and an integer target,
return indices of the two numbers such that they add up to the target.
You may assume that each input would have exactly one solution,
and you may not use the same element twice.
Intuition:
-complement = suppose target is 9 when 2 found then look for
(9-2) = 7 so that sum will be(2+7) 9
-we will store the element and its index in HashMap when we find a compliment
(target - ele) of that element, we will store the indexes.
**/
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hm = new HashMap();
int[] ans = new int[2];
for(int i = 0; i < nums.length; i++)
{
if(hm.containsKey(target - nums[i]))
{
ans[0] = hm.get(target - nums[i]);
ans[1] = i;
}
hm.put(nums[i], i);
}
return ans;
}
}
/**
Time Complexity - O(n) visits each element of the array only once
Space Complexity - O(n) HashMap has been used
**/
4. Group Anagram (leetcode link)
/**
Intuition:
1. Brute Force:
using 2 pointer from index 0 to n when pointer1 is at index i move pointer j
from i to n check all character in i place is same in j if same than add to
list and after iterating second loop add the list to main list.
we have to keep track of index too which has been added already
for(i -> n)
{
key1 =sort a copy of strs[i];
for(j = i -> n)
{
ArrayList al
key2 = sort a copy of strs[j]
if(key2 == key1)
al.add(strs[j])
}
ans.add(al); //ans is List<List<Integer>>
}
return ans;
Time : n^2 * K logK
2. Optimal Solution
create map for each element look the frequencey in a-z and based on it add list in map
**/
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map<String, List<String>> ans = new HashMap();
for (String s : strs) {
// sorting on k time by using fact that all character falls under a-z
int[] count = new int[26];
for (char c : s.toCharArray())
{
count[c - 'a']++;
}
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < 26; i++) {
sb.append('#');// is to distinguish between 1#2 or 12# say we want to say count is 1,2 or 12
sb.append(count[i]);
}
String key = sb.toString();
if (!ans.containsKey(key))
ans.put(key, new ArrayList());
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
}
5. Longest Consecutive Sequence (leetcode link)
/**
Brute force - sort array and compare the neighbour element like nums[i] == nums[i - 1] +1
but it will take n logn time and we have to solve in n time.
Input: nums = [100,4,200,1,3,2]
Output: 4
Intution building:
{100, 4, 200, 1, 3, 2 } in a set
-100 do we have 99 no so it means 100 is the start of
1 sequence do we have 101 no so it's the end too.
so basically we will start from starting of sequence
and we will increment one until incrimented value not found
**/
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> hs = new HashSet();
int max = 0;
for(int i : nums)
{
hs.add(i);
}
for(int i: nums)
{
//check if it is start of sequence
if(!hs.contains(i - 1))
{
int count = 1;
int num = i+1;
while(hs.contains(num))
{
count++;
num++;
}
max = Math.max(max, count);
}
}
return max;
}
}
6. Maximum Subarray (Kaden's Algorithm) (Leetcode link)
/**
Brut Force O(n^2)
get sum of all sub array using 2 for loop and
return maximum sum by maintaining max at each stage
Optimal
Use Kaden's algorithm while iterating
from 0 to n add current element to sum
and update max with sum but if sum become negative while adding some element reset sum to 0.
**/
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
int sum = 0;
for(int i = 0; i < nums.length; i++)
{
sum += nums[i];
max = Math.max(sum, max);
if(sum < 0)
{
sum = 0;
}
}
return max;
}
}
/**
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
sum = -2
max = -2
sum = 1
max = 1
sum = -2
max = 1
sum = 4
max = 4
sum = 3
max = 4
sum = 5
max = 5
sum = 6
max = 6
sum = 1
max = 6
sum = 5
max = 6
return 6
**/
7. Next Permutation (Leetcode link)
/**
Brut Force: Find all permutation in sorted order Time O(n!)
Optimal:
Observation:
start looking from the last to first if we find any element nums[i] < nums[i+1] than swap
[1,2,3] 2 < 3 so swap [1,3,2] and this is the ans..hahaha..........
but what if we didn't find any element like this let's say given array is [3,2,1]
is 2 < 1 no
is 3 < 2 no
observe this case will hapen when we are at the last permutaion (i.e sorted in descending order)
the next element of [3,2,1] will be [1,2,3]
so pseudocode will be
step 1: look from end to start find index which satisfy
nums[i] < nums[i+1] if no such index found reverse the input array
step 2: swap the index with index on right which is just greater
**/
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int index = -1;
//1. find index
for(int i = n-2; i >= 0; i--)
{
if(nums[i] < nums[i+1])
{
index = i;
break;
}
}
//2. if -1 reverse
if(index == -1)
{
reverse(nums,0,n-1);
return;
}
//3. swap just greater element reverse element from index+1 to last
for(int i = n-1; i>= 0; i--)
{
if(nums[i] > nums[index])
{
swap(nums, i, index);
if(index+1 <= n-1)
reverse(nums,index+1,n-1);
break;
}
}
}
private void reverse(int[] nums, int start, int end)
{
while(start < end)
{
swap(nums, start++, end--);
}
}
private void swap(int[] nums, int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
/***
Input: nums = [1,2,5,4,3]
Output: [1,2i,5,4,3] -> [1,3,5,4,2]
Input: nums = [1,3,2]
Output: [2,1,3]
step 1: find index
step 2: swap the index with index on right which is just greater
*/
8. Maximum Product Subarray (Leetcode link)
/**
Brute Force: use two pointer by pointing at place i and move pointer j from i to end O(n^2)
maxi = min_val
for(i -> n){
product = 1
for(j = i -> n)
product *= nums[j]
maxi = max(maxi,product)
}
Optimal solution Intuition:
[2,3,-2,4]
observation
- when all number is positive max will be product of all
- when number of -ve element is even than max will be product of all
- when number of -ve element is odd max will lie either in left of it or right [2,3,-2,4] here max will be either 6 or 4
so calculating suffix and prifix will keep track of max
- when there is zero than also prefix suffix will work
***if we calculate all prefix suffix from all indeces than max will be in them only
[2,3,-2,4]
prefix = 1 *2 = 2 * 3
suffix = 1 *4 = 4 * -2
**/
class Solution {
public int maxProduct(int[] nums) {
int pre = 1;
int suf = 1;
int n = nums.length;
int ans = Integer.MIN_VALUE;
for(int i = 0 ; i < n; i++)
{
if(pre == 0)
pre = 1;
if(suf == 0)
suf = 1;
pre *= nums[i];
suf *= nums[n - i - 1];
ans = Math.max(Math.max(pre,suf), ans);
}
return ans;
/**
int n = nums.length;
int ans = Integer.MIN_VALUE;
for(int i = 0; i < n; i++)
{
int product = 1;
for(int j = i; j < n; j++)
{
product *= nums[j];
ans = Math.max(product, ans);
}
}
return ans;
*/
}
}
/**
Input: nums = [2,3,-2,4]
pre = 2
suf = 4
ans = 4
pre = 6
suf = -8
ans = 6
pre = -12
suf = -24
ans = 6
pre = -48
suf = -48
ans = 6
**/
9. Majority Element (Moor's voting algorithm) (Leetcode link)
/**
Observation more than n/2 means atlest more than 50%
and there is no way possible to have more than 1 ans
Brute force T = O(n^2) S = O(1): use two for loop
itterate and count if count > n/3 return ans
Using HashMap Time = O(n) S = (n): store (element, count)
in hashmap iterate through map if count > n/3 return ans
Using Moor's Voting Algorithm
we can optimize space Time = O(n) S = (1)
moors's algorithm leverage the fact that if we want more than n/2 majority of an element
say we have ( n/2 + 1) count of an element a and we have other element b, c, d etc
we can say that no matter whatever the count of other elements if we sum them
it will always be lesser than n/2
so we will iterate the elements and let them cancel each other the element
which is majority will always cancel all other element and remans at the end
**/
class Solution {
public int majorityElement(int[] nums) {
int count = 1;
int ele = nums[0];
for(int i = 1; i < nums.length; i++)
{
if(count == 0)
{
ele = nums[i];
}
if(ele!= nums[i])
{
count--;
}
else{
count++;
}
}
//since it's gurented there will be majority element for sure else we have to check and count
return ele;
}
}
10. Trapping Rain Water (Leetcode link)
/**
Intuition:
if we want to trap water we need blocker on left and right and
amount of water trap will always be minimum of left and right if we just have 2 blockers but
if we have many blocker in left and many in right than water trap will be
minimum of maximum height of bars on both the sides and if in bottom we place some rock
than some amount of water will be displace so we can say that final amount of water will be
minimum of maximum height of bars on both the sides minus its own height.
Brute force O(n^2): minimum of maximum height of bars on both the sides minus its own height
ans = 0
for(1 -> n-1)
left_max,right_max = 0
//iterate & search the left part for max bar size
left_max = max(left_max, height[j]);
//iterate & search the right part for max bar size
right_max = max(right_max, height[j]);
ans += min(left_max, right_max) - height[i];
return the ans
Optimal solution using two pointer O(n):
Insted of looking left and right at each element
one by one we will do it simultaniousley using two pointer
initialize left pointer to zero and right to size - 1
while left < right
height[left] < height[right]
left++;
leftMax = Math.max(leftMax, height[left]);
res += leftMax - height[left];
height[right] < height[left]
right--;
rightMax = Math.max(rightMax, height[right]);
res += rightMax - height[right];
return res;
**/
class Solution {
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int leftMax = height[left];
int rightMax = height[right];
int res = 0;
while(left < right)
{
if( leftMax < rightMax)
{
left++;
leftMax = Math.max(leftMax, height[left]);
res += leftMax - height[left];
}else
{
right--;
rightMax = Math.max(rightMax, height[right]);
res += rightMax - height[right];
}
}
return res;
}
}
/**
index = 2
MaxLeft = 1
MaxRight = 3
min(MaxLeft,MaxRight) - h[i] = 1
index = 3
MaxLeft = 1
MaxRight = 3
min(MaxLeft,MaxRight) - h[i] >= 0 ? min(MaxLeft,MaxRight) - h[i]: 0
index = 4
MaxLeft = 2
MaxRight = 3
min(MaxLeft,MaxRight) - h[i] >= 0 ? min(MaxLeft,MaxRight) - h[i]: 0
case 1:
O(n) - time Com
O(n) - space comp
case 2:
[0,1,0,2,1,0,1,3,2,1,2,1]
0(n) - time
O(1)
**/
No comments:
For Query and doubts!