Solving Problems: Arrays and Strings

Common Packages and Methods

from IPython.display import SVG, HTML, IFrame
from IPython.display import display
from graphviz import Source
from collections import deque
from typing import List
from numpy import inf
import operator
import codecs
import os
import re

Two Sums

 

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

Examples

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 103
• 109 <= nums[i] <= 109
• 109 <= target <= 109
• Only one valid answer exists.

Solution

class Solution:
    def twoSum(self, nums: List[int], target: int):
        for i in range(0, len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    print("Output:", [i , j])
                    return 
                
Solution().twoSum(nums=[2,7,11,15], target=9)
Solution().twoSum(nums=[3,2,4], target=6)
Solution().twoSum(nums=[3,3], target=6)

Output: [0, 1]
Output: [1, 2]
Output: [0, 1]

Trapping Rain Water

 

Desciption

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Examples:

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Explanation: The above elevation map (black section) is represented by array [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

Solution 1

# Time Complexity: O(n) ; Space Complexity: O(n)
def trap_1(h: List[int]) -> int:
    vol, N = 0, len(h)
    LM, RM = 0, 0
    RMD = [0] * N
    for j in range(N-1, -1, -1):
        RM = max(RM, h[j])
        RMD[j] = RM
    for i in range(0, N):
        LM = max(LM, h[i])
        vol += min(LM, RMD[i]) - h[i]        
    return vol

print("Output:", trap_1(h = [0,1,0,2,1,0,1,3,2,1,2,1]))

Output: 6

Solution 2

# Works Level by level may trigger Time limit exceeded on higher levels
def trap_2(h: List[int]) -> int:
    if len(h) == 0: return 0
    floors, volume  = max(h), 0
    a = False
    for f in range(floors):
        blocks = []
        for i in range(len(h)):
            if h[i]>0: 
                blocks.append(i)
                if len(blocks) == 2:
                    volume += (blocks[1] - blocks[0])-1
                    blocks = blocks[1:]
                h[i]-=1
    return volume

print("Output:", trap_2(h=[0,1,0,2,1,0,1,3,2,1,2,1]))

Output: 6

Longest Substring Without Repeating Characters

 

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

class Solution:
    def lengthOfLongestSubstring(self, x: str) -> int:
        longest=0
        for i in range(len(x)):
            string = ""
            for j in range(i,len(x)):
                if(x[j] in string): break
                else: string+=x[j]
            if(len(string)>longest):
                longest = len(string)
        print("Output:", longest)

Solution().lengthOfLongestSubstring(x="abcabcbb")

Output: 3

Reorder Data in Log Files

 

You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

• Letter-logs: All words (except the identifier) consist of lowercase English letters.
• Digit-logs: All words (except the identifier) consist of digits.

Reorder these logs so that:

• The letter-logs come before all digit-logs.
• The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
• The digit-logs maintain their relative ordering. Return the final order of the logs.

Example 1:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]
Explanation:
The letter-log contents are all different, so their ordering is "art can", "art zero", "own kit dig".
The digit-logs have a relative order of "dig1 8 1 5 1", "dig2 3 6".

Solution 1

# Time Complexity: O(n) + O(n^2)
class Solution:
    def bubblesort(self, logs):
        for iter_num in range(len(logs)-1,0,-1):
            for idx in range(iter_num):
                lt_1 = logs[idx].split(" ", 1)
                lt_2 = logs[idx+1].split(" ", 1)
                if (lt_1[1] > lt_2[1]) or (lt_1[1] == lt_2[1] and lt_1[0] > lt_2[0]):
                    logs[idx], logs[idx+1] = logs[idx+1], logs[idx]
        return logs
                
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        letter_logs, digit_logs = [], []
        for l in logs:
            lt = l.split(" ", 1)
            if any(char.isdigit() for char in lt[1]):
                digit_logs.append(l)
            else:
                letter_logs.append(l)
        return self.bubblesort(letter_logs) + digit_logs
    
logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
print(Solution().reorderLogFiles(logs))

['let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig1 8 1 5 1', 'dig2 3 6']

3Sum

 

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Solution 1

# Reducing the Problem to a Two Sum Problem
# Runtime: 3528 ms ; Time Complexity (worst): O(n^2)
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res, output = [], []
        nums.sort()
        
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            output_2sum = self.twoSum(nums[i+1:], -nums[i])
            for idx in output_2sum:
                instance = idx+[nums[i]]
                res.append(instance)
                
        for idx in res:
            if idx not in output:
                output.append(idx)
        return output
    
    
    def twoSum(self, nums, target):
        # Time Complexity: O(n)
        seen, res = {}, []
        for i, value in enumerate(nums): 
            remaining = target - nums[i] 
            if remaining in seen: 
                res.append([value, remaining])  
            else:
                seen[value] = i  
        return res

t = Solution().threeSum([-1,0,1,2,-1,-4])
print("Output:", t)

Output: [[1, 0, -1], [2, -1, -1]]

Solution 2

# Using Two Pointers
# Runtime: 856 ms ; Time Complexity (worst): O(n^2)
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        for i in range(len(nums) -2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left = i + 1
            right = len(nums) - 1
            while left < right:  
                temp = nums[i] + nums[left] + nums[right]
                if temp > 0: right -= 1
                elif temp < 0: left += 1
                else:
                    res.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]: left += 1
                    while left < right and nums[right] == nums[right-1]: right -= 1   
                    right -= 1 
                    left += 1 
        return res
    
t = Solution().threeSum([-1,0,1,2,-1,-4])
print("Output:", t)

Output: [[-1, -1, 2], [-1, 0, 1]]

Letter Combinations of a Phone Number

 

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Examples

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Input: digits = ""
Output: []

Input: digits = "2"
Output: ["a","b","c"]

Solution 1

# Using Backtracking ; Time Complexity: O(M^N * N)
# Space complexity: O(N)
# Where,  N is the length of input digits
# M is the number of letters corresponding to a digit
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:  return []
        
        t9 = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", 
              "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        
        def backtrack(idx=0, path=[]):
            if len(digits) == len(path):
                ans.append(''.join(path))
                return
            for l in t9[digits[idx]]:
                backtrack(idx+1, path+[l])
                
        ans = []
        backtrack()
        return ans

t = Solution().letterCombinations("23")
print("Output:", t)

Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']