Middle of the Linked List Python

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

• The number of nodes in the given list will be between 1 and 100.

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def middleNode(self, head: ListNode) -> ListNode:

        pA = head

        if head is None:

            return head

        pA = head

        lA = 0

        while pA:

            lA+=1

            pA =pA.next

        pB = head

        lA = lA//2

        while lA != 0:

            pB = pB.next

            lA -= 1

        return pB if lA % 2 ==0 else pB.next

            

Time Complexity : O(n)

Space Complexity : O(1)

Fast Pointer and Slow Pointer :

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def middleNode(self, head: ListNode) -> ListNode:

        slow = fast = head

        while fast and fast.next:

            slow = slow.next

            fast = fast.next.next

        return slow

    

Time Complexity : O(n)

Space Complexity : O(1)           

            

        

        

Backspace String Compare Python

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

Using stack :

Time Complexity : O(n) n is larger of both lengths of strings

Space Complexity : O(n)

class Solution:

    def backspaceCompare(self, S: str, T: str) -> bool:

        def build(S):

            stack = []

            for i in S:

                if i == '#' and stack:

                    stack.pop()

                elif i !='#':

                    stack.append(i)

            return ''.join(stack)

        return build(S) == build(T)

Using Two Pointers:

class Solution:

    def backspaceCompare(self, S: str, T: str) -> bool:

        def F(S):

            skip = 0

            for i in reversed(S):

                if i == '#':

                    skip+=1

                elif skip:

                    skip -=1

                else:

                    yield i

        return all(x == y for x,y in itertools.zip_longest(F(S),F(T)))

    

            

Time Complexity : O(n)

Space Complexity : O(1)

        

Find Peak Element Python

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.

class Solution:

    def findPeakElement(self, nums: List[int]) -> int:

        l = 0

        r = len(nums)-1

        while(l < r):

            mid = l + (r-l) // 2

            if nums[mid] > nums[mid+1]:

                r = mid

            else:

                l = mid+1

        return l

                

        Time Complexity : O(logn)

        Space Complexity : O(1)

Contains Duplicate Python

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        uniqueset = set()
        for num in nums:
            if num in uniqueset:
                return True
            else:
                uniqueset.add(num)
        return False
     

Time Complexity : O(n) 

Space Complexity : O(n)

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(0,len(nums)-1):
            if nums[i] ==  nums[i+1]:
                return True
        return False

Time Complexity : O(nlogn)

Space Complexity : O(1)

Counting Elements Python

Given an integer array arr, count element x such that x + 1 is also in arr.

If there're duplicates in arr, count them seperately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Example 3:

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Constraints:

• 1 <= arr.length <= 1000
• 0 <= arr[i] <= 1000

 Python : Solution 1

class Solution:

    def countElements(self, arr: List[int]) -> int:

        count = 0

        for x in arr:

            if x+1 in arr:

                count+=1

        return count

Time Complexity : O(n*n) because search in entire list

Space Complexity : O(1)

Python : Solution 2

class Solution:

    def countElements(self, arr: List[int]) -> int:

        hash_set = set(arr)

        count = 0

        for x in arr:

            if x+1 in hash_set:

                count+=1

        return count

Time Complexity : O(n) because search in hash set is O(1) 

Space Complexity : O(n)

Python Solution 3

class Solution:

    def countElements(self, arr: List[int]) -> int:

        arr.sort()

        count = 0

        run_length = 1

        for i in range(len(arr)):

            if arr[i-1] != arr[i]:

                if arr[i-1]+1 == arr[i]:

                    count +=run_length

                run_length = 0

            run_length+=1

        return count

Time Complexity : O(nlogn)

Space Complexity : O(n) to O(1)

Copy List with Random Pointer Python

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000

"""

# Definition for a Node.

class Node:

    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):

        self.val = int(x)

        self.next = next

        self.random = random

"""

class Solution:        

    def copyRandomList(self,head):

        if not head:

            return head

        ptr = head

        while ptr:

            new_node = Node(ptr.val,None,None)

            new_node.next = ptr.next

            ptr.next = new_node

            ptr = new_node.next

            

        ptr = head

        

        while ptr:

            new_node = ptr.next

            new_node.random = ptr.random.next if ptr.random else None

            ptr = new_node.next

            

        old_ptr = head

        new_ptr = head.next

        final_ptr = head.next

        while old_ptr:

            old_ptr.next = old_ptr.next.next if old_ptr.next else None

            new_ptr.next = new_ptr.next.next if new_ptr.next else None

            old_ptr = old_ptr.next

            new_ptr = new_ptr.next

            

        return final_ptr

Time Complexity : O(n)

Space Complexity :O(1)

            

        

            

            

        

            

        

        

        

        

        

        

        

        

Copy List with Random Pointer Python

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000.

"""

# Definition for a Node.

class Node:

    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):

        self.val = int(x)

        self.next = next

        self.random = random

"""

class Solution:

    def __init__(self):

        self.visited = {}

    

    def getclonedNode(self,node):

        if node:

            if node in self.visited:

                return self.visited[node]

            else:

                self.visited[node] = Node(node.val,None,None)

                return self.visited[node]

        return None

        

        

        

    def copyRandomList(self,head):

        if not head:

            return head

        old_node = head

        new_node = self.getclonedNode(old_node)

        

        while old_node != None:

            new_node.next = self.getclonedNode(old_node.next)

            new_node.random = self.getclonedNode(old_node.random)

            

            new_node = new_node.next

            old_node = old_node.next

        return self.visited[head]

        

        

        

       Time Complexity : O(n)

       Space Complexity : O(n)