arrays

Question 1

1. 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.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Answer 1

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

    nums.sort()

    left = 0
    right = len(nums)-1

    while left < right:
        if nums[left]+ nums[right] == target:
            return [left, right]

        elif nums[left] + nums[right] < target:
            left += 1
        elif nums[left] + nums[right] > target:
            right -= 1

Question 2

4. Median of Two Sorted Arrays
   Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000

Answer 2

def findMedianSortedArrays(nums1, nums2):

sortedNum = nums1 + nums2

sortedNum = sorted(sortedNum)

if len(sortedNum)%2 == 0:
    medianIndex = (len(sortedNum))//2
    medianNumber = (sortedNum[medianIndex] + sortedNum[medianIndex-1])/2
    return medianNumber
else:
    medianIndex = len(sortedNum)//2 
    medianNumber = sortedNum[medianIndex]
    return medianNumber

Question 3

121. Best Time to Buy and Sell Stock
     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.
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.

Answer 3

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        minn = prices[0]
        maxx = 0

        for num in prices:
            if num < minn:
                minn = num
            elif num > minn:
                d = num - minn
                maxx = max(maxx,d)
        return maxx

Question 4

136. Single Number
     Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Answer 4

from collections import Counter

def singleNumber(nums):

dictA = Counter(nums)

for num in nums:
    if dictA[num] == 1:

        print (num)
print ("none")

Question 5

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Answer 5

def search (nums, target):

left = 0
right = len(nums)-1

while left < right:

        if nums[left] == target:
            return left
        elif nums[left] < target:
            left += 1
    return 'none'

Question 6

fill in the blanks

given an array containing none values fill in the None values with the most recent

array1 = [1, None, 2, 3, None, NOne, 5, None]

Answer 6

def fillBlanks(array):
nums = []
valid = 0
for i in array:

        if i != None:
            nums.append(i)
            valid = i
        else:
            nums.append(valid)
    return nums

Question 7

217. 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.

Answer 7

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        count = collections.Counter(nums)

    for num in nums:
        if count[num] >= 2:

            return True

Question 8

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Answer 8

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        current_subarray = max_subarray = nums[0]

    for num in nums[1:]:

        current_subarray = max(num, current_subarray + num)
        max_subarray = max(max_subarray, current_subarray)

    return max_subarray