Arrays - ashishranjandev/interview-wiki GitHub Wiki
Contains Duplicate - https://leetcode.com/problems/contains-duplicate/
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
public boolean containsDuplicate(int[] nums) {
Set<Integer> intSet = new HashSet<>();
for (int num: nums) {
if (intSet.contains(num)) {
return true;
}
intSet.add(num);
}
return false;
}Valid Anagram - https://leetcode.com/problems/valid-anagram/
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.
public boolean isAnagram(String s, String t) {
int[] str1Arr = new int[26];
int[] str2Arr = new int[26];
for (Character ch : s.toCharArray()) {
int value = str1Arr[ch-97];
str1Arr[ch-97] = ++value;
}
for (Character ch : t.toCharArray()) {
int value = str2Arr[ch-97];
str2Arr[ch-97] = ++value;
}
for (int i = 0; i < 26; i++) {
if (str1Arr[i] != str2Arr[i]) {
return false;
}
}
return true;
}Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
public boolean isValidSudoku(char[][] board) {
HashSet<String> seen =new HashSet();
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
char val=board[i][j];
if(val!='.'){
if(!seen.add(val+"found in row"+i)||
!seen.add(val+"found in column"+ j)||
!seen.add(val+"found in box"+i/3+"-"+j/3))return false;
}
}
}
return true;
}Product of Array Except Self - https://leetcode.com/problems/product-of-array-except-self/
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}Two Sum - https://leetcode.com/problems/two-sum/
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> intSet = new HashMap<>();
int[] answer = new int[2];
int index = 0;
for(int num : nums) {
if(intSet.containsKey(target - num)) {
answer[0] = intSet.get(target - num);
answer[1] = index;
return answer;
}
intSet.put(num, index);
index++;
}
return answer;
}Top K Frequent Elements - https://leetcode.com/problems/top-k-frequent-elements/
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer>[] bucket = new List[nums.length + 1];
Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
for (int n : nums) {
frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
}
for (int key : frequencyMap.keySet()) {
int frequency = frequencyMap.get(key);
if (bucket[frequency] == null) {
bucket[frequency] = new ArrayList<>();
}
bucket[frequency].add(key);
}
List<Integer> res = new ArrayList<>();
for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; pos--) {
if (bucket[pos] != null) {
res.addAll(bucket[pos]);
}
}
return res;
}Longest Consecutive Sequence - https://leetcode.com/problems/longest-consecutive-sequence/
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
public int longestConsecutive(int[] num) {
int res = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int n : num) {
if (!map.containsKey(n)) {
int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
// sum: length of the sequence n is in
int sum = left + right + 1;
map.put(n, sum);
// keep track of the max length
res = Math.max(res, sum);
// extend the length to the boundary(s)
// of the sequence
// will do nothing if n has no neighbors
map.put(n - left, sum);
map.put(n + right, sum);
}
else {
// duplicates
continue;
}
}
return res;
}Group Anagrams - https://leetcode.com/problems/group-anagrams/
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
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.
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> values = new HashMap<>();
int[] valCodeArr = new int[26];
for (String str : strs) {
for (Character ch : str.toCharArray()) {
int value = valCodeArr[ch - 97];
valCodeArr[ch - 97] = ++value;
}
String key = getCode(valCodeArr);
if (values.containsKey(key)) {
List<String> valueList = values.get(key);
valueList.add(str);
values.put(key, valueList);
} else {
List<String> valueList = new ArrayList<>();
valueList.add(str);
values.put(key, valueList);
}
for (int i = 0; i < valCodeArr.length ; i++) {
valCodeArr[i] = 0;
}
}
List<List<String>> output = new ArrayList<>();
for (Map.Entry<String, List<String>> entry : values.entrySet()) {
output.add(entry.getValue());
}
return output;
}
private String getCode(int[] valCodeArr) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < valCodeArr.length; i++) {
sb.append((char) i);
sb.append(valCodeArr[i]);
}
return sb.toString();
}1 Maximum and Minimum Element in an Array 2 Reverse the Array 3 Maximum-Subarray 4 Contains Duplicate 5 Chocolate Distribution Problem 6 Search in Rotated Sorted Array 7 Next Permutation 8 Best time to Buy and Sell Stock 9 Repeat and Missing Number Array 10 Kth-Largest Element in an Array 11 Trapping Rain Water 12 Product of Array Except Self 13 Maximum Product Subarray 14 Find Minimum in Rotated Sorted Array 15 Find Pair with Sum in Sorted & Rotated Array 16 3Sum 17 Container With Most Water 18 Given Sum Pair 19 Kth - Smallest Element 20 Merge Overlapping Intervals 21 Find Minimum Number of Merge Operations to Make an Array Palindrome 22 Given an Array of Numbers Arrange the Numbers to Form the Biggest Number 22 Space Optimization Using Bit Manipulations 23 Subarray Sum Divisible K 24 Print all Possible Combinations of r Elements in a Given Array of Size n 25 Mo's Algorithm