Solving Arrays Problems - AlgoExpert
15 questions about Arrays.
1. Two Number Sum
Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return an empty array.
Scala
import java.util.Arrays;
object SumTwoNumbers {
def main(args: Array[String]): Unit = {
val input_array = Array( -21, 301, 12, 4, 65, 56, 210, 356, 9, -47)
println(twoNumberSum1(input_array,163).toList)
println(twoNumberSum2(input_array,163).toList)
}
def twoNumberSum1(array:Array[Int], targetSum:Int) : Array[Int]= {
var i =0;
for ( i <- 0 to array.length){
var firstNum = array(i);
var secondNum = targetSum -firstNum
if (array contains(secondNum)) {
return Array(firstNum, secondNum)
}
}
return Array()
}
// Time complexity O(nlogn) | Space complexity O(1)
def twoNumberSum2(array: Array[Int], targetSum: Int ): Array[Int] = {
Arrays.sort(array);
var left = 0;
var right = array.length -1;
while (left < right){
var currentSum = array(left) + array(right);
if (currentSum == targetSum){
return Array(array(left), array(right));
}
else if (currentSum < targetSum){
left+=1;
}
else if (currentSum > targetSum){
right-=1;
}
}
return Array()
}
}
// output: [-47,210]
Python
# # O(n^2) time | O(1) space
-----------------------Solution 1 -----------------------------------------
def twoNumberSum(array, targetSum):
# Write your code here.
for i in range(0,len(array)):
for j in range(1,len(array)):
if (array[i] + array[j] == targetSum ) and (i != j):
return [array[i] , array[j] ]
return []
# # O(n^2) time | O(1) space
---------------------------Solution 2-------------------------------------
def twoNumberSum(array, targetSum):
# Write your code here.
for i in range(0,len(array)-1):
for j in range(i+1,len(array)):
if (array[i] + array[j] == targetSum ) and (i != j):
return [array[i] , array[j] ]
return []
# # O(n) time | O(n) space
---------------------------Solution 3-------------------------------------
def twoNumberSum(array, targetSum):
# Write your code here.
for i in range(0,len(array)):
firstNumber = array[i]
secondNumber = targetSum - firstNumber
if secondNumber in array[i+1:]:
return sorted([firstNumber, secondNumber])
return []
# # O(nlogn) time | O(1) space
---------------------------Solution 4-------------------------------------
def twoNumberSum(array, targetSum):
# Write your code here.
array.sort()
left = 0
right = len(array) -1
while left < right:
currentSum = array[left] + array[right]
if currentSum == targetSum:
return [array[left] , array[right]]
elif currentSum < targetSum:
left+=1
elif currentSum > targetSum:
right-=1
return []
Java
// # O(nlogn) time | O(1) space
////---------------------------Solution-------------------------------------
import java.util.*;
class Main {
public static void main(String[] args) {
int[] input_array = new int[]{ -21, 301, 12, 4, 65, 56, 210, 356, 9, -47};
System.out.println(Arrays.toString(twoNumberSum(input_array, 163)));
}
public static int[] twoNumberSum(int[] array, int targetSum) {
// Write your code here.
Arrays.sort(array);
int left;
left = 0;
int right ;
right = array.length -1 ;
while (left < right ) {
int currentSum ;
currentSum = array[left] + array[right];
if ( currentSum == targetSum){
return new int[] {array[left] , array[right]};
}
else if ( currentSum < targetSum){
left+=1;
}
else if ( currentSum > targetSum){
right-=1;
}
}
return new int[] {};
}
}
output: [-47, 210]
2. Validate Subsequence
Given two non-empty arrays of integers, write a function that determines whether the second array is a subsequence of the first one.
A subsequence of an array is a set of numbers that aren't necessarily adjacent in the array but that are in the same order as they appear in the array. For instance, the number [1, 3, 4] from a subsequence of the array [1, 2, 3, 4], and so do the numbers [2, 4]. Note that a single number in an array itself are both valid subsequence of the array.
For this problem, we have 2 approaches:
for loopwhile loopPython
# Time: O(n) | Space: O(1)
def isValidSubsequence(array, sequence):
# Write your code here.
idx=0
seq_length = len(sequence)
for element in array:
if element == sequence[idx]:
idx+=1
if idx == seq_length:
return True
return False
# Time: O(n) | Space: O(1)
def isValidSubsequence(array, sequence):
seqIdx = 0
for value in array:
if seqIdx == len(sequence):
return True
if sequence[seqIdx] == value:
seqIdx += 1
return seqIdx == len(sequence)
# Time: O(n) | Space: O(1)
def isValidSubsequence(array, sequence):
seqIdx = 0
arrIdx = 0
while arrIdx < len(array) and seqIdx < len(sequence):
if array[arrIdx] == sequence[seqIdx]:
seqIdx += 1
arrIdx += 1
return seqIdx == len(sequence)
#{
# "array": [5, 1, 22, 25, 6, -1, 8, 10],
# "sequence": [5, 1, 22, 22, 25, 6, -1, 8, 10]
#}
# result: Flase
print(isValidSubsequence(array,sequence))
3. Three Number Sum
For this problem, there are 2 solutions:
for loopsleft and right with while loop inside a for loopPython
# O(n^3) time | O(n) space
def threeNumberSum(array, targetSum):
array.sort()
# Write your code here.
output = []
for i in range(0,len(array)-2):
for j in range(i+1,len(array)-1):
for k in range(j+1,len(array)):
if ((array[i] + array[j] + array[k]) == targetSum) :
output.append([array[i], array[j], array[k]])
return output
# O(n^2) time | O(n) space
def threeNumberSum(array, targetSum):
# Write your code here.
array.sort() # nlogn
print(array)
results = []
for current in range(len(array)):
left = current + 1
right = len(array) - 1
while left < right:
print( array[current], array[left], array[right])
result = array[current] + array[left] + array[right]
if result == targetSum:
results.append([array[current], array[left], array[right]])
left += 1
right -= 1
elif result < targetSum:
left += 1
else:
right -= 1
return results
print(threeNumberSum([12, 3, 1, 2, -6, 5, -8, 6],0 ))
#[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]
4. Smallest Difference
For this problem, we have 2 solutions:
for loopswhile loopPython
# O(n^2) time | O(1) space
def smallestDifference(arrayOne, arrayTwo):
# Write your code here.
smallest_pair= [None,None]
smallest_value = None
for arrOneIdx in range(0,len(arrayOne),1):
for arrTwoIdx in range(0,len(arrayTwo),1):
abs_diff = abs(arrayOne[arrOneIdx] - arrayTwo[arrTwoIdx])
if arrOneIdx == 0 and arrTwoIdx == 0:
smallest_value = abs_diff
continue
if abs_diff < smallest_value:
smallest_value = abs_diff
smallest_pair[0] = arrayOne[arrOneIdx]
smallest_pair[1] = arrayTwo[arrTwoIdx]
return smallest_pair
# O(n^2) time | O(1) space
# float('inf'), float('-inf')
def smallestDifference(arrayOne, arrayTwo):
# Write your code here.
smallest = [float('inf'), float('-inf')]
for one in arrayOne:
for two in arrayTwo:
if abs(smallest[0] - smallest[1]) > abs(one - two):
smallest = [one, two]
return smallest
# O(nlog(n) + mlog(m)) time (because the length of the two arrays are different)
# O(1) space
def smallestDifference(arrayOne, arrayTwo):
arrayOne, arrayTwo = sorted(arrayOne), sorted(arrayTwo)
smallest=[float("inf"), float("-inf")]
arrOneIdx, arrTwoIdx = 0 , 0
while ((arrOneIdx < len(arrayOne)) and (arrTwoIdx < len(arrayTwo))):
if abs(smallest[0]-smallest[1]) > abs(arrayOne[arrOneIdx] - arrayTwo[arrTwoIdx]):
smallest[0] = arrayOne[arrOneIdx]
smallest[1] = arrayTwo[arrTwoIdx]
if arrayOne[arrOneIdx] < arrayTwo[arrTwoIdx]:
arrOneIdx += 1
elif arrayOne[arrOneIdx] > arrayTwo[arrTwoIdx]:
arrTwoIdx += 1
else:
break
return smallest
#{
# "arrayOne": [10, 1000],
# "arrayTwo": [-1441, -124, -25, 1014, 1500, 660, 410, 245, 530]
#}
# [1000, 1014]
5. Move Element To End
Python
# O(n^2) time | O(1) space
def moveElementToEnd(array, toMove):
# Write your code here.
final_Array = []
count=0
for element in array:
if element == toMove:
count+=1
else:
final_Array.append(element)
for i in range(0,count):
final_Array.append(toMove)
return final_Array
# O(n) time | O(1) space
# --------------------------------------------------------
def moveElementToEnd(array, toMove):
left, right = 0, len(array) - 1
while left < right:
if array[right] == toMove:
right -= 1
if array[left] != toMove:
left += 1
if array[left] == toMove and array[right] != toMove:
array[left], array[right] = array[right], array[left]
return array
# O(n) time | O(1) space
# --------------------------------------------------------
def moveElementToEnd(array, toMove):
# Write your code here
left, right = 0, len(array) -1
while left < right:
while (left < right) and (array[right] == toMove):
right -= 1
if array[left] == toMove:
temp = array[left]
array[left] = array[right]
array[right] = temp
left +=1
return array
6. Monotonic Array
**A monotonic array is an array that is either non-decreasing or non-increasing**
Python
# 0(n) time | O(1) space
def isMonotonic(array):
# Write your code here.
isNonDecreasing = True
isNonIncreasing = True
for i in range(0, len(array)-1):
if array[i] < array[i+1]:
isNonDecreasing = False
if array[i] > array[i+1]:
isNonIncreasing = False
return isNonIncreasing or isNonDecreasing
# return True or False -> kq la True
# 0(n) time | O(1) space
def isMonotonic(array):
# Write your code here
if len(array) <=2:
return True
for i in range(1, len(array)-1):
prev_element = array[i-1]
curr_element = array[i]
next_element = array[i+1]
if prev_element <= curr_element <= next_element or prev_element >= curr_element >= next_element:
continue
else:
return False
return True
# isMonotonic[-1, -5, -10, -1100, -1101, -1102, -9001]
# result= True
7. Spiral Traverse
Python
## O(N) time complexity | O(N) space complexity
def spiralTraverse(array):
result = []
startingRow, startingColumn, endingRow, endingColumn = 0, 0, len(array)-1, len(array[0])-1
while startingRow <= endingRow and startingColumn <= endingColumn:
for i in range(startingColumn,endingColumn+1):
result.append(array[startingRow][i])
for i in range(startingRow+1,endingRow+1):
result.append(array[i][endingColumn])
for i in range(endingColumn-1,startingColumn-1,-1):
if startingRow == endingRow:
break
result.append(array[endingRow][i])
for i in range(endingRow-1, startingRow,-1):
if startingColumn == endingColumn:
break
result.append(array[i][startingColumn])
startingRow+=1
startingColumn+=1
endingRow-=1
endingColumn-=1
return result
print(spiralTraverse([
[7]]))
print(spiralTraverse([
[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
[10, 9, 8, 7]]))
8. Longest Peak
Python
## O(2n) or O(3n) time because we may visit a number twice or third,
## but we can simplify to O(n) time | O(1) space
def longestPeak(array):
longestLength = 0
idx = 1
while idx < len(array) -1 :
isPeak = array[idx-1] < array[idx] and array[idx] > array[idx+1]
if isPeak == False:
idx+=1
continue
leftIdx = idx-2
rightIdx = idx +2
while leftIdx >= 0 and array[leftIdx] < array[leftIdx+1]:
leftIdx-= 1
while rightIdx < len(array) and array[rightIdx] < array[rightIdx-1] :
rightIdx += 1
currLenth = rightIdx - leftIdx -1
longestLength = max(longestLength, currLenth)
idx = rightIdx
return longestLength
# {"array": [1, 2, 3, 3, 4, 0, 10]}
# result = 3
# {"array": [1, 2, 3, 2, 1, 1]}
# result = 5
9. Array of Product
Python
## -------------------------------
## O(n^2) time | O(n) space
def arrayOfProducts(array):
# Write your code here.
result = []
for i in range(len(array)):
runningProduct = 1
for j in range(len(array)):
if j != i:
runningProduct *= array[j]
result.append(runningProduct)
return result
## -------------------------------
## O(n) time | O(n) space
def arrayOfProducts(array):
product = [1 for _ in range(len(array))]
leftRunningProduct = 1
for i in range(len(array)):
product[i] = leftRunningProduct
leftRunningProduct *= array[i]
print(product)
rightRunningProduct =1
print(leftRunningProduct)
for i in reversed(range(len(array))):
product[i] *= rightRunningProduct
rightRunningProduct *= array[i]
print(leftRunningProduct)
print(product)
print(rightRunningProduct)
arrayOfProducts([5, 1, 4, 2])
##-------------------------------
## O(n) time | O(n) space
def arrayOfProducts(array):
# Write your code here.
result = []
for idx in range(0,len(array),1):
runningProduct = 1
leftidx = idx-1
rightidx = idx +1
while leftidx >= 0:
runningProduct *= array[leftidx]
leftidx -= 1
while rightidx <= (len(array) -1) :
runningProduct *= array[rightidx]
rightidx += 1
result.append(runningProduct)
return result
# {"array": [5, 1, 4, 2]}
# [8, 40, 10, 20]
10. Find first duplicate value with constraint
Python
# O(n) time | O(n) space
# using Dictionary to store
def firstDuplicateValue(array):
# Write your code here.
eleDict = {}
for i in array:
if i not in eleDict:
eleDict[i] = 1
else:
return i
return -1
# O(n) time | O(n) space
# using Set to store
def firstDuplicateValue(array):
# Write your code here.
seen = set()
for i in array:
if i not in seen:
seen.add(i)
else:
return i
return -1
# O(N) time | O(1) space
def firstDuplicateValue(array):
# Write your code here.
for value in array:
if array[abs(value)-1] < 0:
return abs(value)
array[abs(value) -1] *= -1
return -1
print(firstDuplicateValue([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10]))
print(firstDuplicateValue([2, 1, 1]))
11. Four Number Sum
Python
