Array
# |
✥ | Title | Difficulty |
|---|---|---|---|
| 1 | ✅ | Summary Ranges | Medium |
| 2 | ✅ | Majority Element | Easy |
| 3 | ✅ | Majority Element II | Easy |
| 4 | ✅ | Intersection of Two Arrays | Easy |
| 5 | ✅ | Intersection of Two Arrays II | Easy |
| 6 | ✅ | Contains Duplicate | Easy |
| 7 | ✅ | Contains Duplicate II | Easy |
| 8 | ✅ | Remove Duplicates from Sorted Array | Easy |
| 9 | ✅ | Remove Duplicates from Sorted Array II | Medium |
| 10 | ✅ | Move Zeroes | Easy |
| 11 | ✅ | Remove Element | Easy |
| 12 | ✅ | Two Sum | Easy |
| 13 | ✅ | 3Sum | Medium |
| 14 | ✅ | 3Sum Closest | Medium |
| 15 | ✅ | 4Sum | Medium |
| 16 | ✅ | Shortest Word Distance | Easy |
| 17 | Shortest Word Distance II | Medium | |
| 18 | ✅ | Shortest Word Distance III | Medium |
| 19 | ✅ | Maximum Size Subarray Sum Equals k | Easy |
| 20 | ✅ | Product of Array Except Self | Medium |
| 21 | ✅ | Rotate Array | Easy |
| 22 | ✅ | Rotate Image | Medium |
| 23 | ✅ | Spiral Matrix | Medium |
| 24 | ✅ | Spiral Matrix II | Medium |
| 25 | ✅ | Valid Sudoku | Easy |
| 26 | ✅ | Set Matrix Zeroes | Medium |
| 27 | ✅ | Next Permutation | Medium |
| 28 | ✅ | Gas Station | Medium |
| 29 | ✅ | Sliding Window Maximum | Hard |
| 30 | ✅ | Longest Consecutive Sequence | Hard |
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
Straight forward method
// Go through from left to right, if found any gaps (nums[i] - nums[i - 1] > 1), construct a string and append it to `res`
class Solution {
func summaryRanges(_ nums: [Int]) -> [String] {
var res: [String] = []
if nums.count == 0 {
return res
}
var start = 0 // last start index
for i in 0..<nums.count {
// if i is the last index, process and break
if i == nums.count - 1 {
if start == i {
res.append("\(nums[i])")
}
else {
res.append("\(nums[start])->\(nums[i])")
}
break
}
// No gap, continue
if nums[i + 1] - nums[i] == 1 {
continue
}
// Process a new string and update start index
else {
if start == i {
res.append("\(nums[i])")
}
else {
res.append("\(nums[start])->\(nums[i])")
}
start = i + 1
}
}
return res
// [1] -> "1"
// [1,3] -> "1", "3"
// [1,2,3] -> "1->3"
// [1,2,3,5,6,9] -> "1->3", "5->6", "9"
// s
// i
}
}#import <Foundation/Foundation.h>
#import <stdio.h>
@interface Solution: NSObject
+ (NSArray *)summaryRange:(NSArray *)nums;
@end
@implementation Solution
+ (NSArray *)summaryRange:(NSArray *)nums
{
NSMutableArray *res = [NSMutableArray new];
if (nums.count == 0) {
return res;
}
NSInteger start = 0;
for (NSInteger i = 0; i < nums.count; i++) {
if (i == nums.count - 1) {
if (start == i) {
[res addObject:[NSString stringWithFormat:@"%@", nums[i]]];
}
else {
[res addObject:[NSString stringWithFormat:@"%@->%@", nums[start], nums[i]]];
}
break;
}
if ([nums[i + 1] integerValue] - [nums[i] integerValue] == 1) {
continue;
}
else {
if (start == i) {
[res addObject:[NSString stringWithFormat:@"%ld", (long)[nums[i] integerValue]]];
}
else {
[res addObject:[NSString stringWithFormat:@"%ld->%ld", (long)[nums[start] integerValue], (long)[nums[i] integerValue]]];
}
start = i + 1;
}
}
return res;
}
@end
int main (int argc, const char * argv[])
{
@autoreleasepool {
NSArray *nums = @[@1, @2, @3, @5, @6, @8];
NSArray *res = [Solution summaryRange:nums];
NSLog(@"%@", [NSString stringWithFormat:@"%@", res]);
}
}Functional Way
// 先go through numbers，在gap处插入separator (nums[0] - 1, because it's a sorted array, this is guaranteed to be a good separator)，然后split by separator，then process each segment
class Solution {
func summaryRanges(_ nums: [Int]) -> [String] {
guard nums.count > 1 else { return nums.map { return "\($0)" } }
let separator = nums[0] - 1
var processedNums: [Int] = []
for num in nums {
if let lastNum = processedNums.last {
if num - lastNum > 1 {
processedNums.append(separator)
}
processedNums.append(num)
} else {
processedNums.append(num)
}
}
let segments = processedNums.split(separator: separator)
return segments.map { segment -> String in
guard let first = segment.first, let last = segment.last else {
return ""
}
if first == last {
return "\(first)"
} else {
return "\(first)->\(last)"
}
}
}
}Given an array of size n, find the majority element.
The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Use dictionary
// Use a dictionary to record num frequency
class Solution {
func majorityElement(_ nums: [Int]) -> Int {
var numCount: [Int : Int] = [:]
var major: Int = nums[0]
nums.forEach {
if let count = numCount[$0] {
numCount[$0] = count + 1
if count + 1 > nums.count / 2 {
major = $0
}
} else {
numCount[$0] = 1
}
}
return major
}
}#import <Foundation/Foundation.h>
#import <stdio.h>
@interface Solution: NSObject
+ (NSInteger)majorityElement:(NSArray *)nums;
@end
@implementation Solution
+ (NSInteger)majorityElement:(NSArray *)nums
{
NSMutableDictionary *numsCount = [NSMutableDictionary new];
NSInteger major = [nums[0] integerValue];
for (NSNumber *num in nums) {
numsCount[num] = ([numsCount objectForKey:num] == nil) ? @1 : @([numsCount[num] integerValue] + 1);
if ([numsCount[num] integerValue] > (nums.count / 2)) {
major = [num integerValue];
break;
}
}
return major;
}
@end
// Main
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray *nums = @[@1, @3, @3, @3, @5];
NSInteger res = [Solution majorityElement:nums];
NSLog(@"%@", [NSString stringWithFormat:@"%ld", (long)res]);
}
return 0;
}Use Count
// A better solution, just use a count
class Solution {
func majorityElement(_ nums: [Int]) -> Int {
if nums.count == 0 {
// never goes here
return 0
}
var count = 1
var major = nums[0]
for i in 1..<nums.count {
if nums[i] == major {
count += 1
} else {
count -= 1
}
if count == 0 {
major = nums[i]
count = 1
}
}
return major
}
}#import <Foundation/Foundation.h>
#import <stdio.h>
@interface Solution: NSObject
+ (NSInteger)majorityElement:(NSArray *)nums;
@end
@implementation Solution
+ (NSInteger)majorityElement:(NSArray *)nums
{
if (nums.count == 0) {
return 0;
}
NSInteger count = 1;
NSInteger major = [nums[0] integerValue];
for (int i = 1; i < nums.count; i++) {
if ([nums[i] integerValue] == major) {
count += 1;
}
else {
count -= 1;
}
if (count == 0) {
major = [nums[i] integerValue];
count = 1;
}
}
return major;
}
@end
int main (int argc, const char * argv[])
{
@autoreleasepool {
NSArray *nums = @[@1, @2, @2, @2, @6, @8];
NSInteger res = [Solution majorityElement:nums];
NSLog(@"%@", [NSString stringWithFormat:@"%ld", (long)res]);
}
}Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
Use 2 Count
// Since there are at most 2 major elements, use two `count`s and `major`s to record majors, and needs to verify those potential majors are actually majors.
class Solution {
func majorityElement(_ nums: [Int]) -> [Int] {
var count1 = 0
var count2 = 0
var major1: Int?
var major2: Int?
for num in nums {
if let major1 = major1, major1 == num {
count1 += 1
}
else if let major2 = major2, major2 == num {
count2 += 1
}
else if count1 == 0 {
major1 = num
count1 += 1
}
else if count2 == 0 {
major2 = num
count2 += 1
}
else {
count1 -= 1
count2 -= 1
}
}
count1 = 0
count2 = 0
for num in nums {
if num == major1 {
count1 += 1
}
else if num == major2 {
count2 += 1
}
}
var res = [Int]()
if count1 > nums.count / 3 {
res.append(major1!)
}
if count2 > nums.count / 3 {
res.append(major2!)
}
return res
}
}Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
- Each element in the result must be unique.
- The result can be in any order.
Use Set
class Solution {
func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var results = Set<Int>()
for num1 in nums1 {
for num2 in nums2 {
if num1 == num2 {
results.insert(num1)
}
}
}
return Array(results)
}
}#import <Foundation/Foundation.h>
#import <stdio.h>
@interface Solution: NSObject
+ (NSArray *)intersection:(NSArray *)nums1 with:(NSArray *)nums2;
@end
@implementation Solution
+ (NSArray *)intersection:(NSArray *)nums1 with:(NSArray *)nums2
{
NSMutableSet *res = [NSMutableSet new];
for (NSNumber *num1 in nums1) {
for (NSNumber *num2 in nums2) {
if (num1 == num2) {
[res addObject:num1];
}
}
}
return [res allObjects];
}
@end
// Main
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray *nums1 = @[@1, @3, @3, @3, @5];
NSArray *nums2 = @[@2, @3, @3, @6];
NSArray *res = [Solution intersection:nums1 with:nums2];
NSLog(@"%@", [NSString stringWithFormat:@"%@", res]);
}
return 0;
}Set Intersection
class Solution {
func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
return Array(Set<Int>(nums1).intersection(Set<Int>(nums2)))
}
}#import <Foundation/Foundation.h>
#import <stdio.h>
@interface Solution: NSObject
+ (NSArray *)intersection:(NSArray *)nums1 with:(NSArray *)nums2;
@end
@implementation Solution
+ (NSArray *)intersection:(NSArray *)nums1 with:(NSArray *)nums2
{
NSMutableSet *set1 = [[NSMutableSet alloc] initWithArray:nums1];
NSSet *set2 = [[NSSet alloc] initWithArray:nums2];
[set1 intersectSet:set2];
return [set1 allObjects];
}
@end
// Main
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray *nums1 = @[@1, @3, @3, @3, @5];
NSArray *nums2 = @[@2, @3, @3, @6];
NSArray *res = [Solution intersection:nums1 with:nums2];
NSLog(@"%@", [NSString stringWithFormat:@"%@", res]);
}
return 0;
}Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
Iterate two arrays, remove both if equal
class Solution {
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var mutableNums1 = nums1
var mutableNums2 = nums2
var results: [Int] = []
var i = 0
while i < mutableNums1.count {
for j in 0 ..< mutableNums2.count {
if mutableNums1[i] == mutableNums2[j] {
results.append(mutableNums1[i])
mutableNums1.remove(at: i)
mutableNums2.remove(at: j)
i -= 1
break
}
}
i += 1
}
return results
}
}Sort then use two pointers to check
class Solution {
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var res = [Int]()
if nums1.count == 0 || nums2.count == 0 {
return res
}
let nums1 = nums1.sorted()
let nums2 = nums2.sorted()
var i = 0
var j = 0
while i < nums1.count && j < nums2.count {
if nums1[i] < nums2[j] {
i += 1
}
else if nums1[i] > nums2[j] {
j += 1
}
else {
res.append(nums1[i])
i += 1
j += 1
}
}
return res
}
}Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Use dictionary to check
class Solution {
func containsDuplicate(_ nums: [Int]) -> Bool {
var hash: [Int : Int] = [:]
for num in nums {
if hash[num] == nil {
hash[num] = 0
} else {
return true
}
}
return false
}
}#import <Foundation/Foundation.h>
#import <stdio.h>
@interface Solution: NSObject
+ (BOOL)containsDuplicate:(NSArray *)nums;
@end
@implementation Solution
+ (BOOL)containsDuplicate:(NSArray *)nums
{
NSMutableDictionary *hash = [[NSMutableDictionary alloc] init];
for (NSNumber *num in nums) {
if (hash[num] != nil) {
return YES;
}
else {
hash[num] = @0;
}
}
return NO;
}
@end
// Main
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray *nums = @[@1, @3, @3, @3, @5];
BOOL res = [Solution containsDuplicate:nums];
NSLog(@"%@", res ? @"YES" : @"NO");
}
return 0;
}Compare set.count with array.count
class Solution {
func containsDuplicate(_ nums: [Int]) -> Bool {
return Set<Int>(nums).count < nums.count
}
}#import <Foundation/Foundation.h>
#import <stdio.h>
@interface Solution: NSObject
+ (BOOL)containsDuplicate:(NSArray *)nums;
@end
@implementation Solution
+ (BOOL)containsDuplicate:(NSArray *)nums
{
NSSet *set = [[NSSet alloc] initWithArray:nums];
return set.count < nums.count;
}
@end
// Main
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray *nums = @[@1, @3, @3, @3, @5];
BOOL res = [Solution containsDuplicate:nums];
NSLog(@"%@", res ? @"YES" : @"NO");
}
return 0;
}Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
Use a dictionary to record last index
class Solution {
func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
var hash: [Int : Int] = [:] // key: num, value: lastIndex
for i in 0..<nums.count {
if let lastIndex = hash[nums[i]] {
if i - lastIndex <= k {
return true
} else {
hash[nums[i]] = i
}
}
else {
hash[nums[i]] = i
}
}
return false
}
}#import <Foundation/Foundation.h>
#import <stdio.h>
@interface Solution: NSObject
+ (void)run;
@end
@implementation Solution
+ (void)run
{
NSArray *nums = @[@1, @3, @2, @1, @3, @5];
NSInteger k = 2;
assert([self containsNearbyDuplicate:nums withK:k] == NO);
k = 3;
assert([self containsNearbyDuplicate:nums withK:k] == YES);
}
+ (BOOL)containsNearbyDuplicate:(NSArray *)nums withK:(NSInteger)k
{
NSMutableDictionary *hash = [NSMutableDictionary new];
for (NSInteger i = 0; i < nums.count; i++) {
if (hash[nums[i]] != nil) {
if (i - [hash[nums[i]] integerValue] <= k) {
return YES;
}
}
hash[nums[i]] = [NSNumber numberWithInteger:i];
}
return NO;
}
@end
// Main
int main(int argc, const char * argv[]) {
@autoreleasepool {
[Solution run];
}
return 0;
}Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
Use `lastIndex` to check
class Solution {
func removeDuplicates(_ nums: inout [Int]) -> Int {
guard nums.count > 0 else {
return 0
}
var lastIndex: Int = 0
for num in nums {
if nums[lastIndex] != num {
lastIndex += 1
nums[lastIndex] = num
}
}
return lastIndex + 1
}
}// A cleaner solution
class Solution {
func removeDuplicates(_ nums: inout [Int]) -> Int {
var lastIndex = -1
for i in 0..<nums.count {
if lastIndex == -1 || nums[lastIndex] != nums[i] {
lastIndex += 1
nums[lastIndex] = nums[i]
}
}
return lastIndex + 1
}
}+ (NSInteger)removeDuplicates:(NSMutableArray *)nums
{
NSInteger lastIndex = -1;
for (NSInteger i = 0; i < nums.count; i++) {
// if not equal, move lastIndex and update nums
if (lastIndex == -1 || nums[lastIndex] != nums[i]) {
lastIndex += 1;
nums[lastIndex] = nums[i];
}
}
return lastIndex + 1;
}Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.
Use two indices to record, just compare first index with current num
class Solution {
func removeDuplicates(_ nums: inout [Int]) -> Int {
guard nums.count > 2 else {
return nums.count
}
var lastIndex1: Int = 0
var lastIndex2: Int = 1
for i in 2 ..< nums.count {
if nums[i] != nums[lastIndex1] {
lastIndex1 += 1
lastIndex2 += 1
nums[lastIndex2] = nums[i]
}
}
return lastIndex2 + 1
}
}+ (NSInteger)removeDuplicates:(NSMutableArray *)nums
{
if (nums.count <= 2) {
return nums.count;
}
NSInteger lastIndex1 = 0;
NSInteger lastIndex2 = 1;
for (NSInteger i = 2; i < nums.count; i++) {
if (nums[i] != nums[lastIndex1]) {
lastIndex1 += 1;
lastIndex2 += 1;
nums[lastIndex2] = nums[i];
}
}
return lastIndex2 + 1;
}Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
Use last non zero index
class Solution {
func moveZeroes(_ nums: inout [Int]) {
guard nums.count > 0 else { return }
var lastNonZeroIndex: Int = -1
for i in 0..<nums.count {
let num = nums[i]
if num == 0 {
continue
} else {
lastNonZeroIndex += 1
nums[lastNonZeroIndex] = num
}
}
while lastNonZeroIndex + 1 < nums.count {
lastNonZeroIndex += 1
nums[lastNonZeroIndex] = 0
}
}
}+ (void)moveZeroes:(NSMutableArray *)nums
{
if (nums.count == 0) {
return;
}
NSInteger lastIndex = -1;
for (NSInteger i = 0; i < nums.count; i++) {
if ([nums[i] integerValue] == 0) {
continue;
}
else {
lastIndex += 1;
nums[lastIndex] = nums[i];
}
}
// [1,2,3, -, -, -]
// |
lastIndex += 1;
while (lastIndex < nums.count) {
nums[lastIndex] = @0;
lastIndex += 1;
}
}Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.
Hint:
- Try two pointers.
- Did you use the property of "the order of elements can be changed"?
- What happens when the elements to remove are rare?
Like remove zero
class Solution {
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
// guard nums.count > 0 else { return 0 }
var lastNonValueIndex = -1
for i in 0..<nums.count {
let num = nums[i]
if num == val {
continue
} else {
lastNonValueIndex += 1
nums[lastNonValueIndex] = num
}
}
return lastNonValueIndex + 1
}
}Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.
Use dictionary to store number->index, find target index
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var numToIndex: [Int : Int] = [:]
for i in 0..<nums.count {
let numToFind = target - nums[i]
if let indexToFind = numToIndex[numToFind] {
return [indexToFind, i]
} else {
numToIndex[nums[i]] = i
}
}
return []
}
}+ (NSArray *)twoSum:(NSArray *)nums withTarget:(NSInteger)target
{
NSMutableDictionary *dict = [NSMutableDictionary new];
for (NSInteger i = 0; i < nums.count; i++)
{
NSNumber *toFind = @(target - [nums[i] integerValue]);
if (dict[toFind] != nil)
{
return @[dict[toFind], @(i)];
}
else
{
dict[nums[i]] = @(i);
}
}
return @[];
}Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Iterate from 0 to count - 1, use two pointers to find results, skip if equals
class Solution {
func threeSum(_ nums: [Int]) -> [[Int]] {
var results: [[Int]] = []
guard nums.count >= 3 else { return results }
let nums = nums.sorted()
let target = 0
for i in 0..<(nums.count) {
// Try first element, but skip duplicated nums
if i > 0 && nums[i] == nums[i - 1] {
continue
}
var j = i + 1
var k = nums.count - 1
while j < k {
if nums[i] + nums[j] + nums[k] == target {
results.append([nums[i], nums[j], nums[k]])
j += 1
while nums[j] == nums[j - 1] && j < k {
j += 1
}
k -= 1
while nums[k] == nums[k + 1] && j < k {
k -= 1
}
}
else if nums[i] + nums[j] + nums[k] < target {
j += 1
while nums[j] == nums[j - 1] && j < k {
j += 1
}
}
else {
k -= 1
while nums[k] == nums[k + 1] && j < k {
k -= 1
}
}
}
}
return results
}
}+ (NSArray *)threeSum:(NSArray *)nums
{
NSArray *sortedNums = [nums sortedArrayUsingSelector:@selector(compare:)];
NSMutableArray *res = [NSMutableArray new];
for (NSInteger i = 0; i < sortedNums.count; i++)
{
if (i != 0 && sortedNums[i] == sortedNums[i - 1])
{
continue;
}
NSInteger left = i + 1;
NSInteger right = sortedNums.count - 1;
while (left < right)
{
NSInteger target = 0 - [sortedNums[i] integerValue];
NSInteger leftNumber = [sortedNums[left] integerValue];
NSInteger rightNumber = [sortedNums[right] integerValue];
if (leftNumber + rightNumber < target) {
left += 1;
while (sortedNums[left] == sortedNums[left - 1] && left < right) {
left += 1;
}
}
else if (leftNumber + rightNumber > target) {
right -= 1;
while (sortedNums[right] == sortedNums[right + 1] && left < right) {
right -= 1;
}
}
else {
[res addObject:@[sortedNums[i], sortedNums[left], sortedNums[right]]];
left += 1;
while (sortedNums[left] == sortedNums[left - 1] && left < right) {
left += 1;
}
right -= 1;
while (sortedNums[right] == sortedNums[right + 1] && left < right) {
right -= 1;
}
}
}
}
return res;
}Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Iterate and use two pointers, make sure set initial result
class Solution {
func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
var result: Int = 0
guard nums.count > 2 else { return result } // question to ask
let nums = nums.sorted()
for i in 0..<(nums.count) {
if i > 0 && nums[i] == nums[i - 1] { continue }
var j = i + 1
var k = nums.count - 1
// set initial value
if i == 0 {
result = nums[i] + nums[j] + nums[k]
if result == target {
return result
}
}
while j < k {
let newSum = nums[i] + nums[j] + nums[k]
if abs(newSum - target) < abs(result - target) {
result = newSum
}
if newSum < target {
j += 1
while nums[j] == nums[j - 1] && j < k {
j += 1
}
}
else if newSum > target {
k -= 1
while nums[k] == nums[k + 1] && j < k {
k -= 1
}
}
else {
result = target
break
}
}
}
return result
}
}Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
One extra iteration on 3Sum
class Solution {
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
var results: [[Int]] = []
guard nums.count > 3 else { return results }
let nums = nums.sorted()
for i in 0..<(nums.count) {
if i > 0 && nums[i] == nums[i - 1] { continue }
for j in (i + 1)..<(nums.count) {
if j > (i + 1) && nums[j] == nums[j - 1] { continue }
var a = j + 1
var b = nums.count - 1
while a < b {
let newSum = nums[i] + nums[j] + nums[a] + nums[b]
if newSum < target {
a += 1
while nums[a] == nums[a - 1] && a < b {
a += 1
}
}
else if newSum > target {
b -= 1
while nums[b] == nums[b + 1] && a < b {
b -= 1
}
}
else {
results.append([nums[i], nums[j], nums[a], nums[b]])
a += 1
b -= 1
while nums[a] == nums[a - 1] && a < b {
a += 1
}
while nums[b] == nums[b + 1] && a < b {
b -= 1
}
}
}
}
}
return results
}
}Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.
Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
Use to indices to record last appeared index, record min distance
class Solution {
func shortestDistance(_ words: [String], _ word1: String, _ word2: String) -> Int {
var index1 = -1
var index2 = -1
var res = Int.max
for i in 0..<words.count {
if words[i] == word1 {
index1 = i
}
if words[i] == word2 {
index2 = i
}
if index1 != -1 && index2 != -1 {
res = min(res, abs(index1 - index2))
}
}
return res
}
}+ (NSInteger)shortestDistance:(NSArray *)words word1:(NSString *)word1 word2:(NSString *)word2
{
NSInteger index1 = -1;
NSInteger index2 = -1;
NSInteger res = INT_MAX;
for (NSInteger i = 0; i < words.count; i++) {
if ([words[i] isEqualTo:word1]) {
index1 = i;
}
if ([words[i] isEqualTo:word2]) {
index2 = i;
}
if (index1 != -1 && index2 != -1) {
res = MIN(res, labs(index1 - index2));
}
}
return res;
}This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.
Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
Use a hash map to store indices for words, calculate the minimum distance from two arrays using two pointers
// TODOThis is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = "makes", word2 = "makes", return 3.
Note: You may assume word1 and word2 are both in the list.
Same process for word1 == word2, if equals, use extra `lastChanged` variable to help alternately updating index1 and index2 (用一个辅助变量记录上一次更改过的index，来交替update index)
class Solution {
func shortestWordDistance(_ words: [String], _ word1: String, _ word2: String) -> Int {
var index1 = -1
var index2 = -1
var res = Int.max
if word1 == word2 {
var lastChanged = -1 // either 1 or 2
for i in 0..<words.count {
if words[i] == word1 && lastChanged != 1 {
index1 = i
lastChanged = 1
}
else if words[i] == word2 && lastChanged != 2 {
index2 = i
lastChanged = 2
}
if index1 != -1 && index2 != -1 {
res = min(res, abs(index1 - index2))
}
}
}
else {
for i in 0..<words.count {
if words[i] == word1 {
index1 = i
}
if words[i] == word2 {
index2 = i
}
if index1 != -1 && index2 != -1 {
res = min(res, abs(index1 - index2))
}
}
}
return res
}
}Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.
Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
**Example 1**:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)
**Example 2**:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)
Follow Up: Can you do it in O(n) time?
Use Sum Dictionary
class Solution {
func maxSubArrayLen(_ nums: [Int], _ k: Int) -> Int {
var sumToIndex = [Int : Int]()
sumToIndex[0] = -1 // This is essential
var res = 0
var sum = 0
for i in 0..<nums.count {
sum += nums[i]
if let pre = sumToIndex[sum - k] {
res = max(res, i - pre)
}
// Only update when there's no sum key. Because we want to keep farmost index which has this sum
if sumToIndex[sum] == nil {
sumToIndex[sum] = i
}
}
return res
}
}+ (NSInteger)maxSubArrayLen:(NSArray <NSNumber *> *)nums withK:(NSInteger)k
{
NSMutableDictionary *sumToIndex = [NSMutableDictionary new];
sumToIndex[@0] = @(-1);
NSInteger sum = 0;
NSInteger res = 0;
for (NSInteger i = 0; i < nums.count; i++) {
sum += [nums[i] integerValue];
NSInteger restSum = sum - k;
if (sumToIndex[@(restSum)] != nil) {
res = MAX(res, i - [sumToIndex[@(restSum)] integerValue]);
}
if (sumToIndex[@(sum)] == nil) {
sumToIndex[@(sum)] = @(i);
}
}
return res;
}Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
Use two product dictionary (similar to sum dictionary), one from left to right, another from right to left.
class Solution {
func productExceptSelf(_ nums: [Int]) -> [Int] {
var a = 1
var results: [Int] = []
for i in 0..<nums.count {
results.append(a)
a *= nums[i]
}
a = 1
for i in stride(from: nums.count - 1, to: -1, by: -1) {
results[i] *= a
a *= nums[i]
}
return results
}
}Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Hint:
Could you do it in-place with O(1) extra space?
Related problem: Reverse Words in a String II
Use swift array slice
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
guard nums.isEmpty == false else { return }
let k = k % nums.count
let rightPart = nums[(nums.count - k)..<nums.count]
let leftPart = nums[0..<(nums.count - k)]
nums = Array(rightPart) + Array(leftPart)
}
}Rotate each segments, then rotate the whole segment
// Swift
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
guard nums.isEmpty == false else { return }
let k = k % nums.count
// rotate elements except rest k elements
rotate(&nums, 0, nums.count - k)
// rotate rest k elements
rotate(&nums, nums.count - k, nums.count)
// rotate whole array
rotate(&nums, 0, nums.count)
}
func rotate(_ nums: inout [Int], _ from: Int, _ to: Int) {
guard 0 <= from && from < to && to <= nums.count else { return }
var left = from
var right = to - 1
while left < right {
(nums[left], nums[right]) = (nums[right], nums[left])
left += 1
right -= 1
}
}
}// Objective-C
+ (void)rotate:(NSMutableArray <NSNumber *> *)nums k:(NSInteger)k
{
if (nums.count == 0) {
return;
}
NSInteger reducedK = k % nums.count;
[self rotate:nums from:0 to:nums.count - reducedK];
[self rotate:nums from:nums.count - reducedK to: nums.count];
[self rotate:nums from:0 to:nums.count];
}
+ (void)rotate:(NSMutableArray <NSNumber *> *)nums from:(NSInteger)from to:(NSInteger)to
{
if (!(0 <= from && from < to && to <= nums.count)) {
return;
}
NSInteger times = (to - from) / 2;
NSInteger left = from;
NSInteger right = to - 1;
for (NSInteger i = 0; i < times; i++) {
NSNumber *temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left += 1;
right -= 1;
}
}You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up: Could you do this in-place?
Rotate level by level, then by item
// Swift
class Solution {
func rotate(_ matrix: inout [[Int]]) {
let d = matrix.count
for level in 0..<Int(ceil(Double(d / 2))) {
for j in level..<(d - level - 1) {
(matrix[level][j], matrix[d - j - 1][level], matrix[d - level - 1][d - j - 1], matrix[j][d - level - 1]) =
(matrix[d - j - 1][level], matrix[d - level - 1][d - j - 1], matrix[j][d - level - 1], matrix[level][j])
}
}
}
}Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
Straightforward way, use four directions
class Solution {
func spiralOrder(_ matrix: [[Int]]) -> [Int] {
var results = [Int]()
let m = matrix.count
guard m > 0 else { return results }
let n = matrix[0].count
guard n > 0 else { return results }
var checked: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: m)
var direction: Int = 1
var i = 0
var j = 0
while true {
if checked[i][j] == false {
results.append(matrix[i][j])
checked[i][j] = true
if results.count == m * n {
return results
}
} else {
break
}
switch direction {
case 1:
if j + 1 >= n || checked[i][j + 1] == true {
direction = 2
i += 1
} else {
j += 1
}
case 2:
if i + 1 >= m || checked[i + 1][j] == true {
direction = 3
j -= 1
} else {
i += 1
}
case 3:
if j - 1 < 0 || checked[i][j - 1] == true {
direction = 4
i -= 1
} else {
j -= 1
}
case 4:
if i - 1 < 0 || checked[i - 1][j] == true {
direction = 1
j += 1
} else {
i -= 1
}
default:
break;
}
}
return results
}
}Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
From outer level to inner level, update matrix
class Solution {
func generateMatrix(_ n: Int) -> [[Int]] {
var results: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: n)
guard n > 0 else { return results }
var index = 1
var loop = 0
for loop in 0..<Int(ceil(Double(n) / 2)) {
var i = loop
var j = loop
for j in (0 + loop)..<(n - loop) {
results[i][j] = index
index += 1
}
j = n - 1 - loop
for i in (1 + loop)..<(n - loop) {
results[i][j] = index
index += 1
}
i = n - 1 - loop
for j in stride(from: n - 2 - loop, to: loop - 1, by: -1) {
results[i][j] = index
index += 1
}
j = loop
for i in stride(from: n - 2 - loop, to: loop, by: -1) {
results[i][j] = index
index += 1
}
}
return results
}
}Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
Straightforward way, check row/column/block
class Solution {
func isValidSudoku(_ board: [[Character]]) -> Bool {
return checkRow(board) && checkColumn(board) && checkBlock(board)
}
private func checkRow(_ board: [[Character]]) -> Bool {
for row in board {
if haveDuplicates(row.flatMap({ Int(String($0)) })) {
return false
}
}
return true
}
private func checkColumn(_ board: [[Character]]) -> Bool {
for j in 0..<9 {
var col: [Int] = []
for i in 0..<9 {
if let num = Int(String(board[i][j])) {
col.append(num)
}
}
if haveDuplicates(col) {
return false
}
}
return true
}
private func checkBlock(_ board: [[Character]]) -> Bool {
// for each big block
for i in 0..<3 {
for j in 0..<3 {
var nums = [Int]()
for x in (i * 3)..<(i * 3 + 3) {
for y in (j * 3)..<(j * 3 + 3) {
if let num = Int(String(board[x][y])) {
nums.append(num)
}
}
}
if haveDuplicates(nums) {
return false
}
}
}
return true
}
private func haveDuplicates(_ nums: [Int]) -> Bool {
guard nums.count > 0 else { return false }
var check = Set<Int>()
for num in nums {
let (inserted, _) = check.insert(num)
if inserted == false {
return true
}
}
return false
}
}Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
- Did you use extra space?
- A straight forward solution using O(mn) space is probably a bad idea.
- A simple improvement uses O(m + n) space, but still not the best solution.
- Could you devise a constant space solution?
Use first row and first col to record zeroes, also need to check whether the first row/col already has zero
class Solution {
func setZeroes(_ matrix: inout [[Int]]) {
guard matrix.count > 0 else { return }
let m = matrix.count
guard matrix[0].count > 0 else { return }
let n = matrix[0].count
var row0HasZero = false
var col0HasZero = false
// check row0
for j in 0..<n {
if matrix[0][j] == 0 {
row0HasZero = true
break
}
}
// check col0
for i in 0..<m {
if matrix[i][0] == 0 {
col0HasZero = true
break
}
}
// check rest, update row0 and col0
for i in 0..<m {
for j in 0..<n {
if i == 0 || j == 0 {
continue
}
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
// update with row0
for j in 1..<n {
if matrix[0][j] == 0 {
// update the col
for i in 0..<m {
matrix[i][j] = 0
}
}
}
// update with col0
for i in 1..<m {
if matrix[i][0] == 0 {
// update the row
for j in 0..<n {
matrix[i][j] = 0
}
}
}
// update row0 if row0 has zero
if row0HasZero {
for j in 0..<n {
matrix[0][j] = 0
}
}
// update col0 if col0 has zero
if col0HasZero {
for i in 0..<m {
matrix[i][0] = 0
}
}
}
}Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples.
Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
A solution needs to be memorized
class Solution {
func nextPermutation(_ nums: inout [Int]) {
var k = -1 // the index that nums[k] < nums[k + 1]
for i in stride(from: nums.count - 2, to: -1, by: -1) {
if nums[i] < nums[i + 1] {
k = i
break
}
}
// Descending order, just reverse it
if k == -1 {
nums.reverse()
return
}
var l = -1 // the largest index that nums[l] > nums[k]
for i in stride(from: nums.count - 1, to: k, by: -1) {
if nums[i] > nums[k] {
l = i
break
}
}
// Swap k and l
(nums[k], nums[l]) = (nums[l], nums[k])
// reverse from k + 1 to end
reverse(&nums, k + 1, nums.count)
}
func reverse(_ nums: inout [Int], _ from: Int, _ to: Int) {
var left = from
var right = to - 1
while left < right {
(nums[left], nums[right]) = (nums[right], nums[left])
left += 1
right -= 1
}
}
}There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note: The solution is guaranteed to be unique.
A solution needs to be memorized
class Solution {
func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
let count = gas.count
if count == 0 {
return -1
}
var start = count - 1
var end = 0
var sum = gas[start] - cost[start]
while start > end {
if sum >= 0 {
sum += gas[end] - cost[end]
end += 1
}
else {
start -= 1
sum += gas[start] - cost[start]
}
}
return sum >= 0 ? start : -1
}
}Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as [3,3,5,5,6,7].
Note: You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up: Could you solve it in linear time?
Hint:
- How about using a data structure such as deque (double-ended queue)?
- The queue size need not be the same as the window’s size.
- Remove redundant elements and the queue should store only elements that need to be considered.
A solution needs to be memorized
class Solution {
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
var res: [Int] = []
var q: [Int] = [] // indices
for i in 0..<nums.count {
// Check whether the first element is still in the window, if not, remove it
if let first = q.first, first < i - k + 1 { // i - k + 1 is the first index of window
q.removeFirst()
}
// Check the coming element, clear smaller elements
while q.isEmpty == false && nums[q.last!] < nums[i] {
q.removeLast()
}
q.append(i)
// Record if needed, if has more than k elements
if (i - k + 1 >= 0) {
res.append(nums[q.first!])
}
}
return res
}
}Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
For each num, expand to left and to right. Use a hash to help
class Solution {
// Basic idea is use a hash to record whether the num is checked
// Then for each num, expand to right and expand to left, stops when it's checked or not in the dictionary
func longestConsecutive(_ nums: [Int]) -> Int {
// Use a hash to store whether this num has been checked
var checked: [Int : Bool] = [:]
for i in 0..<nums.count {
checked[nums[i]] = false
}
var res = 1
for i in 0..<nums.count {
// If current num has been checked, skip
if checked[nums[i]] == true {
continue
}
// Include current num, the length is 1
var length = 1
// Expand to right
var right = nums[i] + 1
while checked[right] == false { // nil or true won't continue
length += 1
checked[right] = true
right += 1
}
// Expand to left
var left = nums[i] - 1
while checked[left] == false { // nil or true won't continue
length += 1
checked[left] = true
left -= 1
}
res = max(res, length)
}
return res
}
}