Array Flashcards
[Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant extra space.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
Example 2:
Input: nums = [1,1,2]
Output: [1]
Example 3:
Input: nums = [1]
Output: []
class Solution {
public List<Integer> findDuplicates(int[] nums) {
// 4 -3 -2 -7 -3 -1
List<Integer> li = new ArrayList<>();
for(int i =0;i<nums.length;i++){
int index = Math.abs(nums[i])-1;
nums[index]= nums[index]*-1 ;
if(nums[index]>0){
li.add(index+1);
}
}
return li;
}
}</Integer></Integer>
- Unique Number of Occurrences
Easy
Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.
Example 1:
Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.
Example 2:
Input: arr = [1,2]
Output: false
Example 3:
Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true
class Solution {
public boolean uniqueOccurrences(int[] arr) {
HashMap<Integer, Integer> hm = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
hm.put(arr[i], hm.getOrDefault(arr[i], 0) + 1);
}
Set<Integer> set = hm.keySet();
HashSet<Integer> hs = new HashSet<>();
for (Integer i : set) {
if (!hs.contains(hm.get(i))) {
hs.add(hm.get(i));
} else {
return false;
}
}
return true;</Integer></Integer>
} }
- Intersection of Two Arrays
Easy
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> s = new HashSet<>();
Set<Integer> f = new HashSet<>();
for(int i =0;i<nums1.length;i++){
s.add(nums1[i]);
}
for(int i =0;i<nums2.length;i++){
if(s.contains(nums2[i])){
f.add(nums2[i]);
}
}
int[] output = new int[f.size()];
int length = 0;
for(Integer i : f){
output[length]=i;
length++;
}
return output;
}
}</Integer></Integer>
- Replace Elements with Greatest Element on Right Side
Easy
Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.
After doing so, return the array.
Example 1:
Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation:
- index 0 –> the greatest element to the right of index 0 is index 1 (18).
- index 1 –> the greatest element to the right of index 1 is index 4 (6).
- index 2 –> the greatest element to the right of index 2 is index 4 (6).
- index 3 –> the greatest element to the right of index 3 is index 4 (6).
- index 4 –> the greatest element to the right of index 4 is index 5 (1).
- index 5 –> there are no elements to the right of index 5, so we put -1.
class Solution {
public int[] replaceElements(int[] arr) {
for(int i =0;i<arr.length;i++){
int max_val = -1;
for(int j = i+1;j<arr.length;j++){
if(arr[j]>max_val){
max_val = arr[j];
}
}
arr[i]=max_val;
}
return arr;
} }
- Unique Email Addresses
Easy
Every valid email consists of a local name and a domain name, separated by the ‘@’ sign. Besides lowercase letters, the email may contain one or more ‘.’ or ‘+’.
For example, in “alice@leetcode.com”, “alice” is the local name, and “leetcode.com” is the domain name.
If you add periods ‘.’ between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. Note that this rule does not apply to domain names.
For example, “alice.z@leetcode.com” and “alicez@leetcode.com” forward to the same email address.
If you add a plus ‘+’ in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered. Note that this rule does not apply to domain names.
For example, “m.y+name@email.com” will be forwarded to “my@email.com”.
It is possible to use both of these rules at the same time.
Given an array of strings emails where we send one email to each emails[i], return the number of different addresses that actually receive mails.
Example 1:
Input: emails = [“test.email+alex@leetcode.com”,”test.e.mail+bob.cathy@leetcode.com”,”testemail+david@lee.tcode.com”]
Output: 2
Explanation: “testemail@leetcode.com” and “testemail@lee.tcode.com” actually receive mails.
Example 2:
Input: emails = [“a@leetcode.com”,”b@leetcode.com”,”c@leetcode.com”]
Output: 3
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> hs = new HashSet<>();
for(int i =0;i<emails.length;i++){
StringBuilder sb = new StringBuilder();
String[] prefixArray = emails[i].split("@");
String[] furtherPrefix = prefixArray[0].split("\\+");
String prefixFinal = furtherPrefix[0].replaceAll("\\.","");
sb.append(prefixFinal).append("@").append(prefixArray[1]);
System.out.println(sb);
hs.add(sb.toString());
}
return hs.size();
} }
- Best Time to Buy and Sell Stock
Easy
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
class Solution {
public int maxProfit(int[] prices) {
int minValue =Integer.MAX_VALUE;
int profit = 0;
int maxProfit=0
for(int i = 0;i<prices.length;i++){
minValue=Math.min(minValue,prices[i]);
profit = prices[i]-minValue;
if(profit>maxProfit){
maxProfit = profit;
}
}
return maxProfit;
} }
- Merge Sorted Array
Easy
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Example 3:
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
m =m-1;
n = n-1;
int curr = nums1.length-1;
while(curr>=0){
if(m<0){
nums1[curr]=nums2[n];
n--;
curr--;
}
else if(n<0){
nums1[curr]=nums1[m];
m--;
curr--;
}
else {
if(nums2[n]>nums1[m]){
nums1[curr]=nums2[n];
curr--;
n--;
}
else {
nums1[curr]=nums1[m];
curr--;
m--;
}
}
} } }
- Peak Index in a Mountain Array
Medium
An array arr is a mountain if the following properties hold:
arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < … < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > … > arr[arr.length - 1]
Given a mountain array arr, return the index i such that arr[0] < arr[1] < … < arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1].
You must solve it in O(log(arr.length)) time complexity.
Example 1:
Input: arr = [0,1,0]
Output: 1
Example 2:
Input: arr = [0,2,1,0]
Output: 1
Example 3:
Input: arr = [0,10,5,2]
Output: 1
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0;
int right = arr.length-1;
while(left<=right){
int mid = (left+right)/2;
if(arr[mid]>arr[mid+1] && arr[mid]>arr[mid-1]){
return mid;
}
else if(arr[mid]<arr[mid+1]){
left = mid+1;
}
else{
right = mid;
}
}
return -1;
} }
- Find Peak Element(multiple peaks)
Medium
11.2K
4.5K
company
Facebook
company
Amazon
c
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
class Solution {
public int findPeakElement(int[] arr) {
if(arr.length==1) return 0;
if(arr[0] > arr[1]) return 0;
if(arr[arr.length-2] < arr[arr.length-1]) return arr.length-1;
int left = 0;
int right = arr.length-1;
while(left<=right){
int mid = (left+right)/2;
if(arr[mid]>arr[mid+1] && arr[mid]>arr[mid-1]){
return mid;
}
else if(arr[mid]<arr[mid+1]){
left = mid+1;
}
else{
right = mid;
}
}
return -1;
- Group Anagrams
Medium
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.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Example 2:
Input: strs = [””]
Output: [[””]]
Example 3:
Input: strs = [“a”]
Output: [[“a”]]
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> output = new ArrayList<>();
Map<String,List<String>> hm = new HashMap<>();
for(int i =0;i<strs.length;i++){
String s = strs[i];
char[] charArr = s.toCharArray();
Arrays.sort(charArr);
System.out.println(charArr);
if(!hm.containsKey(String.valueOf(charArr)))
hm.put(String.valueOf(charArr),new ArrayList<String>());
hm.get(String.valueOf(charArr)).add(s);
}
Set<String> set = hm.keySet();
for(String s : set){
output.add(hm.get(s));
}
return output;</String></String></String></String></String>
} }
- Kth Largest Element in an Array
Medium
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
class Solution {
public int findKthLargest(int[] nums, int k) {
//1,2,2,3,3,4,5,5,6
//1,2,3,4,5,6
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0;i<nums.length;i++){
pq.add(nums[i]);
}
for(int i =0;i<nums.length-k;i++){
pq.poll();
}
return pq.poll();
}
}</Integer>
- Best Time to Buy and Sell Stock II
Medium
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
class Solution {
public int maxProfit(int[] prices) {
int minValue = prices[0];
int maxValue = prices[0];
int maxProfit = 0;
int x=0;
while(x<prices.length-1){
while(x<prices.length-1 && prices[x]>=prices[x+1]){
x++;
}
minValue = prices[x];
while(x<prices.length-1 && prices[x]<=prices[x+1]){
x++;
}
maxValue = prices[x];
maxProfit = maxProfit + maxValue - minValue;
}
return maxProfit;
} }
- Product of Array Except Self
Medium
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.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
class Solution {
public int[] productExceptSelf(int[] nums) {
int preffixProd = 1;
int suffixProd = 1;
int[] result = new int[nums.length];
result[0]=1;
for(int i =1;i<nums.length;i++){
preffixProd = preffixProd *nums[i-1];
result[i]=preffixProd;
}
for(int j=nums.length-2;j>=0;j--){
suffixProd = suffixProd * nums[j+1];
result[j]= result[j] * suffixProd;
}
return result;
} }
- Top K Frequent Elements
Medium
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int[] output = new int[k];
for(int i =0;i<nums.length;i++){
map.put(nums[i], map.getOrDefault(nums[i],0)+1);
}
List<Integer> list = new ArrayList<>(map.keySet());
Collections.sort(list,(a, b)->map.get(b)-map.get(a));</Integer>
for(int i =0;i<output.length;i++){
output[i]=list.get(i);
}
return output;
} }
- Find the Duplicate Number
Medium
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
class Solution {
public int findDuplicate(int[] nums) {
int l =0;
int r=nums.length-1;
int dup =-1;
while(l<=r){
int mid = l+(r-l)/2;
int count=count(nums,mid);
if(count>mid){
dup=mid;
r=mid-1;
}
else
l=mid+1;
}
return dup;
}
private int count(int[] nums, int mid){
int count=0;
for(int i=0;i<nums.length;i++){
if(nums[i]<=mid)
count++;
}
return count;
} }
