Leetcode Study Plan — Data Structures (Day 1)

The problems that are part of Day 1 of Leetcode’s Data Structures Study Plan are as follows:

1. (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.

Examples:

Input: nums = [1,2,3,1]
Output: true
Input: nums = [1,2,3,4]
Output: false
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Code:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

Time complexity: O(n) ... n = length of nums

Space complexity: O(n) ... n = length of nums

Approach:

• Get the length of the input list nums and the length of the set of nums (the set will contain all unique values within nums)
• If both lengths are not equal, return True as there are duplicates in nums
• If both lengths are equal return False as all elements in nums are unique

2. (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.

Examples:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Input: nums = [1]
Output: 1
Input: nums = [5,4,-1,7,8]
Output: 23

Code:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        curr_max = global_max = nums[0]
        
        for num in nums[1:]:
            curr_max = max(num, curr_max + num)
            global_max = max(curr_max, global_max)
        
        return global_max

Time complexity: O(n) ... n = length of nums

Space complexity: O(1) ... the space required by the program does not increase as the input size (length of nums) increases

Approach:

• Set the current max and global max to the first element of the input list nums
• Loop over the remainder of nums … set the current max to the current number in the loop or the sum of the current number and current max … set the global max to the max of current max or the global max so far
• Return the global max

This concludes the problems for Day 1 of the study plan.