Problem Solving Python Part 2

Problems

1. Valid Parentheses:

    Given a string containing just the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid.

 .....................................................................................................................................................................

2. Merge Intervals:

    Given a collection of intervals, merge all overlapping intervals.

......................................................................................................................................................................

3. Product of Array Except Self:

    Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

......................................................................................................................................................................

4. Top K Frequent Elements:

    Given a non-empty array of integers, return the k most frequent elements.

..................................................................................................................................................................... 

5. Search in Rotated Sorted Array:

 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array, return its index, otherwise return -1.

......................................................................................................................................................................

Solutions 

Solution 1

def is_valid(s):

        stack = []

        mapping = {')': '(', '}': '{', ']': '['}

        for char in s:

            if char in mapping:

                top_element = stack.pop() if stack else '#'

                if mapping[char] != top_element:

                    return False

            else:

                stack.append(char)

        return not stack

    s = "()[]{}"

    print(is_valid(s))  # Output: True

......................................................................................................................................................................

Solution 2

def merge_intervals(intervals):

        intervals.sort(key=lambda x: x[0])

        merged = []

        for interval in intervals:

            if not merged or merged[-1][1] < interval[0]:

                merged.append(interval)

            else:

                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

    intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

    print(merge_intervals(intervals))  # Output: [[1, 6], [8, 10], [15, 18]]

......................................................................................................................................................................

Solution 3

 def product_except_self(nums):

        length = len(nums)

        answer = [0] * length

        answer[0] = 1

        for i in range(1, length):

            answer[i] = nums[i - 1] * answer[i - 1]

        R = 1

        for i in reversed(range(length)):

            answer[i] = answer[i] * R

            R *= nums[i]

        return answer

    nums = [1, 2, 3, 4]

    print(product_except_self(nums))  # Output: [24, 12, 8, 6]

......................................................................................................................................................................

Solution 4

from collections import Counter

    import heapq

    def top_k_frequent(nums, k):

        count = Counter(nums)

        return heapq.nlargest(k, count.keys(), key=count.get)

    nums = [1, 1, 1, 2, 2, 3]

    k = 2

    print(top_k_frequent(nums, k))  # Output: [1, 2]

......................................................................................................................................................................

Solution 5

def search(nums, target):

        left, right = 0, len(nums) - 1

        while left <= right:

            mid = (left + right) // 2

            if nums[mid] == target:

                return mid

            if nums[left] <= nums[mid]:

                if nums[left] <= target