Q: Lists (inplace)

lists_questions.py

##### 1. List (Rotate)
You are given a list of n integers and a non-negative integer k.

Your task is to write a function called rotate that takes the list of integers and an integer k as input and rotates the 
list to the right by k steps. The function should modify the input list in-place, and you should not return anything.
Constraints:
    Each element of the input list is an integer.
    The integer k is non-negative.

Function signature: def rotate(nums, k):
Example:
Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: nums = [5, 6, 7, 1, 2, 3, 4] 

## Solution
def rotate(nums, k):
    if len(nums) < 2 or k == 0: return nums 
    k = k % len(nums)
    nums[:] = nums[-k:] + nums[:-k]
    
######## 2. List: Remove Duplicates 
Given a sorted list of integers, rearrange the list in-place such that all unique elements appear at the beginning of the list.
Your function should return the new length of the list containing only unique elements. 
Note that you should not create a new list or use any additional data structures to solve this problem. 
The original list should be modified in-place.

Constraints:
    The input list is sorted in non-decreasing order.
    The input list may contain duplicates.
    The function should have a time complexity of O(n), where n is the length of the input list.
    The function should have a space complexity of O(1).

## Solution
#2-pointer approach (i--> read; j--> write)
def remove_duplicates(my_list):
    if len(my_list) == 0: return 0
    
    j = 0 #unique element pointer 
    for i in range(1, len(my_list)):
        if my_list[i] != my_list[j]:
            j += 1
            my_list[j] = my_list[i]
    return j + 1

######### 3. List: MaxSub Array
Given an array of integers nums, write a function max_subarray(nums) that finds the contiguous subarray (containing 
at least one number) with the largest sum and returns its sum.
Remember to also account for an array with 0 items.

Input: A list of integers nums.
Output: An integer representing the sum of the contiguous subarray with the largest sum.
Example:
    max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])
    Output: 6
    Explanation: The contiguous subarray [4, -1, 2, 1] has the largest sum, which is 6.

# Solution
def max_subarray(my_list):
    if len(my_list) == 0: return 0 
    max_sum = my_list[0] #global_max 
    curr_sum = my_list[0] #local sum pointer 
    
    for num in my_list[1:]:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(curr_sum, max_sum)
        
    return max_sum

####### 4. List Subarray Sum
Given an array of integers nums and a target integer target, write a Python function called subarray_sum that finds 
the indices of a contiguous subarray in nums that add up to the target sum using a hash table (dictionary).
Note that there may be multiple subarrays that add up to the target sum, 
but your function only needs to return the indices of any one such subarray. 

Your function should take two arguments:
    nums: a list of integers representing the input array (may be positive or negative)
    target: an integer representing the target sum

Your function should return a list of two integers representing the starting and ending indices of the subarray that 
adds up to the target sum. If there is no such subarray, your function should return an empty list.
For example:
    nums = [1, 2, 3, 4, 5] target = 9
    print(subarray_sum(nums, target))  # should print [1, 3]

# Solution
def subarray_sum(nums, target):
    seen = {0: -1}
    cs = 0
    for i, num in enumerate(nums):
        cs += num 
        diff = cs - target  
        if diff in seen:
            return [seen[diff] + 1, i]
        else:
            seen[cs] = i 
    return []