Leetcode

Some leetcode questions for security roles

Two Sum

Difficulty	Easy
Topics	arrrays, hashmap

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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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 <= 104

• 109 <= nums[i] <= 109

• 109 <= target <= 109

• Only one valid answer exists.

Follow-up:

Can you come up with an algorithm that is less than

O(n2)

time complexity?

Solution: Bruteforce

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = set()
        for x in range(0,len(nums)):
            for y in range(0,len(nums)):
                if x == y:
                    continue
                if nums[x] + nums[y] == target:
                    result.add(x)
                    result.add(y)
        return result
        

Solution 2: Use hashmap:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        hashmap = {}
        for x in range(0, len(nums)):
            minus_data = target - nums[x]
            if minus_data in hashmap:
                result.append(hashmap[minus_data])
                result.append(x)
            hashmap[nums[x]] = x
        return result

Two Sum II - Input Array Is Sorted

Difficulty	medium
Topics	arrrays, two pointers

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated so that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. 
Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. 
We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. 
We return [1, 2].

Constraints:

• 2 <= numbers.length <= 3 * 104

• -1000 <= numbers[i] <= 1000

• numbers is sorted in non-decreasing order.

• -1000 <= target <= 1000

• The tests are generated so that there is exactly one solution.

Solution

// Some code

Additional Resources

Contains Duplicate

Additional Resources

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.

• void push(int val) pushes the element val onto the stack.

• void pop() removes the element on the top of the stack.

• int top() gets the top element of the stack.

• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

• 231 <= val <= 231 - 1

• Methods pop, top and getMin operations will always be called on non-empty stacks.

• At most 3 * 104 calls will be made to push, pop, top, and getMin.

Solution

class MinStack(object):

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        val = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(val)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def top(self):
        return self.stack[-1] if self.stack else None

    def getMin(self):
        return self.min_stack[-1] if self.min_stack else None
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

Additional Resources

Valid Parentheses

Merge Two Sorted List

Daily Temperatures