Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example Input: [4,3,2,7,8,2,3,1] Output: [5,6] Solution class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: N = len(nums) result = [] for num in nums: pos = abs(num) % N if nums[pos] > 0: nums[pos] = -nums[pos] for i in range(1, N+1): if nums[i%N] > 0: result.

by lek tin in "algorithm" access_time 1-min read

Maximum Swap

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get. Example 1 Input: 2736 Output: 7236 Explanation: Swap the number 2 and the number 7. Example 2 Input: 9973 Output: 9973 Explanation: No swap. Note The given number is in the range [0, 10^8] Solution class Solution: def maximumSwap(self, num: int) -> int: numChars = list(str(num)) n = len(numChars) last = [0 for i in range(10)] for i in range(n): last[ord(numChars[i])-ord("0")] = i for i in range(n): # test the biggest number first j = 9 # We wanna find out the largest digit on the right while j > int(ord(numChars[i])-ord("0")): if last[j] > i: temp = numChars[i] numChars[i] = numChars[last[j]] numChars[last[j]] = temp return int("".

by lek tin in "algorithm" access_time 1-min read

Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime? Example: Input: [4,3,2,7,8,2,3,1] Output: [2,3] Solution # Time: O(n) # Space: O(1) class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: """ :type nums: List[int] :rtype: List[int] """ result = [] for i in nums: if nums[abs(i)-1] < 0: result.

by lek tin in "algorithm" access_time 1-min read

Squares of a Sorted Array

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order. Example 1 Input: [-4,-1,0,3,10] Output: [0,1,9,16,100] Example 2 Input: [-7,-3,2,3,11] Output: [4,9,9,49,121] Note 1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A is sorted in non-decreasing order. Solution class Solution: def sortedSquares(self, A: List[int]) -> List[int]: result = A[:] leftPtr, rightPtr = 0, len(A)-1 i = 0 while leftPtr <= rightPtr: i += 1 if abs(A[leftPtr]) <= abs(A[rightPtr]): result[-i] = A[rightPtr] * A[rightPtr] rightPtr -= 1 else: result[-i] = A[leftPtr] * A[leftPtr] leftPtr += 1 return result

by lek tin in "algorithm" access_time 1-min read

Intersection of Three Sorted Arrays

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays. Example 1: Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8] Output: [1,5] Explanation: Only 1 and 5 appeared in the three arrays. Constraints: 1 <= arr1.length, arr2.length, arr3.length <= 1000 1 <= arr1[i], arr2[i], arr3[i] <= 2000 Solution Python

by lek tin in "algorithm" access_time 1-min read

Longest Continuous Increasing Subsequence

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray). Example 1 Input: [1,3,5,4,7] Output: 3 Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4. Example 2 Input: [2,2,2,2,2] Output: 1 Explanation: The longest continuous increasing subsequence is [2], its length is 1.

by lek tin in "algorithm" access_time 1-min read

Arrays in Python

Reverse an array arr = [1, 2, 3, 4, 5, 6, 7, 8] reversedArray = arr[::-1] # [8, 7, 6, 5, 4, 3, 2, 1] arr[3:5] = arr[3:5][::-1] Slices with step s[i:j:k] means “slice of s from i to j with step k”. When i and j are absent, the whole sequence is assumed and thus s[::k] means “every k-th item” in the entire sequence. s = range(20) # output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] # 3rd item from s: s[::3] # output: [0, 3, 6, 9, 12, 15, 18] # 3rd item from s[2:]: s[2:] # output: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] s[2::3] # output: [2, 5, 8, 11, 14, 17] # 3rd item from s[5:12]: s[5:12] # output: [5, 6, 7, 8, 9, 10, 11] s[5:12:3] # output: [5, 8, 11] # 3rd item from s[:10]: s[:10] # output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] s[:10:3] # output: [0, 3, 6, 9] Clone a list newArr = oldArr[:]

by lek tin in "programming-language" access_time 2-min read

Arrays in CPP

To get the number of elements in an array in C++: sizeof(awesomeArray) = total number of bytes allocated for awesomeArray array. Divide it with the size of one element in the array will give you the number of elements in the array: sizeof(awesomeArray)/sizeof(awesomeArray[0])

by lek tin in "programming-language" access_time 1-min read

Product of Array Except Self

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]. Solution 1 Time: O(n) Space: O(n) class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: left, right = [nums[0]], [nums[-1]] N = len(nums) if N <= 1: return 0 res = [] for i in range(1, N-1): left.

by lek tin in "algorithm" access_time 1-min read

Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1 Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123.

by lek tin in "algorithm" access_time 1-min read