Tag: software engineer interviews

Posted in Arrays and Strings, coding interview preparation, Data Structures/ Leetcode, Leetcode Top 150, Two Pointer Technique

[Problem Solving] Remove duplicates in a sorted array in-place

Posted on by Swetha Kannan

Problem Statement

Given an array of integers sorted in increasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Return k after placing the final result in the first k slots of nums.

Examples

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

This is one of my favorite and easy array problems to start thinking in terms of two pointers to solve array problems. Why two pointers in this case?

We need a pointer that will read the elements of the array one by one. We can use another pointer to overwrite the elements in place. Also whenever we want to modify elements of an array in place – think about whether the two pointer technique can be applied!

The read pointer, let’s say r is pretty straightforward where we increment its value by one during each iteration. The only problem to solve here is to understand when to move the write w pointer.

In this problem, we are going to always compare two elements to each other to find out if it is a repeated value. This naturally leads to maintaining two variables prev and curr to keep track of the previous element to compare the current one with. Now for moving the write pointer,

  • Each time prev = curr, we move the read pointer r and not the write pointer w. This is so that we keep reading the elements until we find the element to overwrite with.
  • When prev != curr, we can now overwrite the array element, increment w and r as well as set prev to curr.

Let’s see how this works using the following diagram. Note that only r and w are variables that we use for the two pointer technique here. Prev and curr are variables to keep track of the previous and current elements.

Complexity

O(N) to traverse the array and O(1) space since we modify the array in-place.

Solution

def removeDuplicates(self, nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return 1
             
    r, w = 1, 1
    prev = nums[0]
    while (r < len(nums) and w < len(nums)):
        curr = nums[r]
        if prev != curr:
            nums[w] = curr
            w += 1
            prev = curr
        r += 1
    return w

Hope you enjoyed learning to solve this array problem with the two pointer technique.

Posted in Data Structures/ Leetcode

Monotonic Stack

Posted on by Swetha Kannan

Today let us learn about monotonic stacks and their usage.

A monotonic stack is one in which the elements of the stack are always increasing or decreasing. This ensures that the stack is always sorted in some order. Some interesting applications of monotonic stacks are to

  • Find the next smaller or greater element in an array
  • Find the previous smaller or greater element in an array
  • Find the minimum or maximum element in a sliding window etc.

Let’s take a look at an example problem below.

Find the next greater element in an array

The next greater of an element X in an array is the first greater element to the right side of X. For example:

[1, 2, 3, 4]

  • Next greater element (1) => 2
  • Next greater element (2) => 3
  • Next greater element (3) => 4

In this problem, we can use a monotonic stack to push elements into and keep popping the elements as long as the top most element has a value smaller than the current element whose next greater element we want to find. That’s a mouthful, so let’s look at an example!

We have the following array.

Input: [1, 3, 4, 2, 5] and here’s an array of the next first greater elements to the right of each element in the array.

Output: [3, 4, 5, 5, -1] (-1 when no next greater element exists)

Algorithm:

  • Iterate the given array from i = 0 to i = N – 1.
  • Push the element array[i] in the monotonic stack if either the stack is empty or the top of stack > array[i]. We are thereby building a monotonic stack decreasing from the bottom to top.
  • In this process, we have to pop the elements in stack if they are lesser than array[i] which is the first greater element found to the right of the popped one.

Look at how the stack and the mapping changes as we iterate the array in the following diagram.

Finally push 5.

Time Complexity: O(N) where N is the size of the array that is iterated. This is because we iterate the array only once and each element is pushed and popped exactly once.

Space Complexity: O(N) since the mapping and the stack will contain at most N elements.

Code:

In the following code nums1 contains the elements whose next greater element should be found in nums2.

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        num_to_next_greater_mapping = collections.defaultdict(lambda: -1)
        mono_stack = []
        
        for index, val in enumerate(nums2):
            if mono_stack and val > mono_stack[-1]:
                while mono_stack and mono_stack[-1] < val:
                    num_to_next_greater_mapping[mono_stack[-1]] = val
                    mono_stack.pop(-1)
            mono_stack.append(val)
            
        results = []
        for n in nums1:
            results.append(num_to_next_greater_mapping[n])
            
        return results

Stay tuned for more of these problems in this space.

Posted in Arrays and Strings, Data Structures/ Leetcode, Recursion

Regular Expression Matching

Posted on by Swetha Kannan

Given an input string and a regex pattern, implement regular expression matching with support for ‘.’ and ‘*’.

  • ‘.’ matches any single character
  • ‘*’ matches zero or more of the preceding element (the char before *)

Examples

  1. s = ‘aa’, p = ‘ab’ Not a match
  2. s= ‘bbbbb’, p = ‘b*’ Match because ‘*’ matches zero or more of the preceding element b
  3. s= ‘fljflf’, p = ‘.*’ Match because we want to match zero or more of the preceding element which is any character in this case
  4. s = ‘oop’, p = ‘r*o*p’ Match because r is present 0 times, o is present twice and p is a direct match

Thought Process

Let’s approach this problem step by step.

Case 1: The simplest case would be when the given string and the pattern do not contain any ‘.’ or ‘*’ characters but only alphabets.

s = 'aa' and p = 'ab'

In this case we would check the string and the pattern from left to right to see if each character in the string matches the characters in the pattern.

a = a matched so far
b != a Match failed so return False

Case 2: When no ‘*’ characters are present but only ‘.’. In this case ‘.’ can match any single character. So we check for that condition and continue to check the remaining characters in the given string and the pattern using recursion.

def isRegexMatch(s, pattern):
    # If pattern is empty, as long as string is also empty => true
    # If pattern is empty but string is not empty => return false
    if not pattern:
        return not s

    # Check the first character match in s and pattern
    # String should not be empty
    # The first characters exactly match (Or)
    # pattern's first char contains "." to match any char in s
    is_first_char_match = len(s) > 0 and (s[0] == pattern[0] or pattern[0] == ".")
    
    # Continue checking the remaining characters using recursion
    return is_first_char_match and isRegexMatch(s[1:], pattern[1:])

Case 3: When the regex pattern contains both ‘.’ and ‘*’ characters, things get a little complicated.

Note that the pattern will never begin with ‘*’ because it denotes that a preceding character can be present 0 or more times. So it will ALWAYS be present only as the second character when that part of the pattern is being processed after a recursive call, For example: a*, .*

So we can have a condition that evaluates this logic as shown below.

if len(pattern) >= 2 and pattern[1] == "*"

If the above condition holds true, then we check regex match differently due to the presence of ‘*’. Let’s think about how we can do that. There are two valid scenarios that are allowed here.

Scenario 1: s = "aaaa", pattern = "c*a*"

In this case len(pattern) = 4 which is >= 2 and pattern[1] = ‘*‘. We see that c is not present in the string s but it can occur zero 0 or more times. In this case we can ignore checking the first two characters of the pattern and continue the recursion as shown below.

isRegexMatch(s, pattern[2:]) => isRegexMatch("aaaa", "a*")

Scenario 2: s = "aaaa", pattern = "a*"

In this case len(pattern) = 2 which is >= 2 and pattern[1] = ‘*‘. s contains ‘a’ which is a direct match with the first character in the pattern. So we check for first character match and continue recursion on the rest of the string. 

is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("aaa", "a*")

Note that we pass the full pattern string to the recursion call here because ‘*’ can match zero or more characters of ‘a’. So we want to check the string for that as well. The following recursive calls will hold true.

isRegexMatch("aaa", "a*") =>
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("aa", "a*")
isRegexMatch("aa", "a*") =>
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("a", "a*")
isRegexMatch("a", "a*") =>
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("", "a*")
isRegexMatch("", "a*") =>
isRegexMatch(s, pattern[2:]) => isRegexMatch("", "") so final result will be true.
if len(pattern) >= 2 and pattern[1] == "*":
    return isRegexMatch(s, pattern[2:]) or (is_first_char_match and isRegexMatch(s[1:], pattern))

Complexity

For a given string of length S and pattern P, we make recursive calls using indexes s[i:] and pattern[2j:] (When ‘*’ is present). The recursive tree can go to a depth of (S+P/2) which will have 2h leaf nodes where h = (S+P/2), so 2(S+P/2) leaf nodes. This means the recursion will branch into 2(S+P/2) sub-problems.

If we pass the entire string and pattern at the worst case, the complexity of solving a sub-problem will be O(S+P). So the time complexity will roughly be

O((S+P) * 2(S+P/2))

To read more about the complexity calculation for this problem, here’s a detailed article.

Putting it all together.

Solution

def isRegexMatch(s, pattern):
    # If pattern is empty, as long as string is also empty => true
    # If pattern is empty but string is not empty => return false
    if not pattern:
        return not s

    # Check the first character match in s and pattern
    # String should not be empty
    # The first characters exactly match (Or)
    # pattern's first char contains "." to match any char in s
    is_first_char_match = len(s) > 0 and (s[0] == pattern[0] or pattern[0] == ".")
    
    # When '*' is present in the second char of pattern
    if len(pattern) >= 2 and pattern[1] == "*":
        return isRegexMatch(s, pattern[2:]) or (is_first_char_match and isRegexMatch(s[1:], pattern))

    else:
        # Continue checking the remaining characters using recursion
        return is_first_char_match and isRegexMatch(s[1:], pattern[1:])

Hope you enjoyed solving the regular expression problem. In the next post, we will look at how to improve upon this solution using Dynamic Programming!

Posted in Arrays and Strings, Data Structures/ Leetcode, Palindromes

Longest Palindromic Substring

Posted on by Swetha Kannan

Problem Statement

Given a string s, we have to return the longest palindromic substring.

Note: Palindromes are words or phrases that read the same backward and forward, letter for letter, number for number, or word for word. Source: Grammarly

Examples

Input: s = “babad”

Output: “bab”

Input: s = “dfgggggkl”

Output: “ggggg”

Input s = “a”

Output: “a”

Thought Process

In any given string, to find the longest palindromic substring, the brute force approach would be to consider every possible substring and then have a helper function to check if it is a palindrome. This results in a cubic complexity for a string of length N. Why O(N3) complexity? To check if a string is a palindrome or not, we will have to traverse through the whole substring. At the worst case, this will be the entire string s. This takes O(N). We will then have to use two for loops to check each possible substring which will be O(N2). Now let’s think of an efficient way of doing this.

There are two types of palindromes.

  • Palindromes with an even number of letters. Examples: “aa”, “abba”, “cdeedc”
  • Palindromes with an odd number of letters. Examples: “a”, “aba”, “cdedc”

The speciality of palindromes is that they expand from a central point and mirror each other on the left and right. How to define what is the center? In an even length palindrome, the center is in between two letters. In “abba”, the center is in between the two “b”s. In “aba”, which is an odd length palindrome, the center is “b”.

How many possible centers are there in a given palindrome?

Example 1: “aba”

The possible centers to consider are a, a <-> b, b, b <-> a, a ie., 5 centers

Example 2: “abba”

The possible centers are a, a <-> b, b, b <-> b, b, b <-> a, a ie., 7 centers

For N = 2, possible centers = 3

For N = 3, possible centers = 5

For N = 4, possible centers = 7

For N = 5, possible centers = 9

Let’s look at the possible centers and see by how much does it go up for each value of N.

(5 – 3) = (7 – 5) = (9 – 7) = 2

We can calculate the number sequence by using xn. In this case x = 2, so 2N. We notice that for N = 3, the possible centers are not 2N = 6, we have to subtract 1. So the generalized sequence will be 2N – 1.

To solve the given problem, we can iterate through each character in the string while considering it as a possible center for a palindrome. We can then expand around this center while checking its left and right side for mirroring. Since there can be odd length and even length palindromes, we have to consider the max length between them.

To get the max odd palindrome, we pass the left and right pointers as the current character since the center is a single character. Example: “aba”, when i = 1 (b), the left and right starting points to expand around will both be “b”, i = 1.

To get the max even palindrome, we pass the left and right pointers as the current and next character since the center is in between two characters. Example: “abba”, when i = 1 (b), the left and right starting points to expand around will be “b”, i = 1 and the next “b”, i = 2.

We can then take the string with the max length between these two values.

longest_palindromic_substring = ""

for i in range(len(s)):
    odd_max = check_palindrome(s, i, i)
    even_max = check_palindrome(s, i, i+1)

    longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len)

Now let’s write a helper function to check if the given string is a palindrome.

def check_palindrome(s, left, right):

    while left >= 0 and right < len(s):

        if s[left] == s[right]: # check mirroring
            left -= 1
            right += 1
        else:  # Break the loop if the characters mismatch
            break  

    return s[left+1: right]

Complexity

O(N2) time – O(N) to expand around each center and O(N) to check if the substring is a palindrome

O(1) space

Putting it all together.

Solution

def find_longest_palindromic_substring:
    
    if not s:
        return s
    
    def check_palindrome(s, left, right):

        while left >= 0 and right < len(s):

            if s[left] == s[right]: # check mirroring
                left -= 1
                right += 1
            else:  # Break the loop if the characters mismatch
                break  

        return s[left+1: right]

    longest_palindromic_substring = ""

    for i in range(len(s)):
        odd_max = check_palindrome(s, i, i)
        even_max = check_palindrome(s, i, i+1)

       longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len) # This will return the max value based on string length (key = len)

    return longest_palindromic_substring

Hope you enjoyed this step by step problem solving approach for the longest palindromic substring problem and learnt a thing or two about palindromes!

Posted in Arrays and Strings, Data Structures/ Leetcode

[Problem Solving] Spiral Matrix

Posted on by Swetha Kannan

Given a matrix of m x n elements, return the elements in spiral order.

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output: [1,2,3,6,9,8,7,4,5]

This problem is quite popular and is frequently asked during interviews.

Solution: To traverse the matrix in spiral order, we have to go along the boundaries starting from the top left element at i = 0, j = 0 where i, j represent the row and column indexes respectively. Let’s view the matrix as a collection of layers. Once we complete the outermost layer, we have to keep traversing the inner layers until no element is left to be visited. We can think of this as traversing multiple matrices in spiral order layer by layer.

Spiral Matrix Traversal

What are some things to remember while traversing?

  • We need some indexes to track our traversal. A straightforward approach is to have four indexes to keep track of the four boundaries of the matrix. These will be called left, right, top and bottom.
  • We will be using a while loop to add elements to a results array as long as left < right and top < bottom. This indicates that there are still elements left to traverse.
  • Inside the while loop, we will be using four for loops to traverse each boundary.
  • Avoid adding duplicate elements when changing directions ie., once we finish traversing a row [1, 2, 3, 4, 5], we have to increment the row index to avoid adding 5 again during the right most column traversal. Similarly, right and bottom pointers should be decremented upon completing their respective boundary traversals.
  • This problem code is nothing fancy but a matter of writing clear code without getting confused with the indices. The best way to get it right is to write the for loops as you traverse an example asymmetric matrix. This is because, a symmetric matrices usually do not help us handle edge cases in matrix problems.
  • One corner case for this problem is when we are traversing a column matrix as shown below where m = 4, n = 1.
Column Matrix

In this case, we first initialize these variables.

top = 0
bottom = m #4
left = 0
right = n #1

Top boundary: row = top = 0, col = left to right [0, 1). Results = [1]. Increment top pointer, top = 1.

Right boundary: row = top to bottom [1, 4), col = right – 1 = 0. Results = [ 1, 2, 3, 4]. Decrement right pointer, right = 0.

Now after the above two for loops, we are done traversing the entire matrix. But the next traversal will add duplicate elements to the results.

Bottom boundary: row = bottom – 1 = 3, col = right – 1 to left – 1 [0, -1). Results = [1, 2, 3, 4, 4]

This will attempt to traverse the bottom element 4 again. So right after traversing top and right boundaries, we have to always check whether left < right and top < bottom condition still holds true. In this case top < bottom since 1 < 4 but left = right since 0 = 0 indicating that we are about to traverse a boundary again.

Time Complexity: We will end up visiting each element of the matrix, so time complexity will be O(M * N).

Space Complexity: Constant variables are used to track boundaries, so no additional space is being used. The space complexity will be O(1).

Code: 

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        top, bottom = 0, m
        left, right = 0, n
        
        results = []
        
        while top < bottom and left < right:
            
            # traverse top boundary
            for i in range(left, right):
                results.append(matrix[top][i])
            top += 1
                
            # traverse right boundary
            for i in range(top, bottom):
                results.append(matrix[i][right-1])
            right -= 1
            
            if top < bottom and left < right:
                # traverse bottom boundary
                for i in range(right - 1, left - 1, -1):
                    results.append(matrix[bottom-1][i])
                bottom -= 1

                # traverse left boundary
                for i in range(bottom - 1, top - 1, -1):
                    results.append(matrix[i][left])
                left += 1
            
        return results

Testing: The following cases are good to test for matrix problems.

  • Empty matrix: []
  • Empty rows: [[]]
  • Single value matrix: [[1]]
  • Two element matrix: [[1, 2]]
  • Column matrix: [[1,2,3,4]]
  • Row matrix: [[1],[2],[3],[4]]
  • Symmetric matrix: [[1,2,3, 4],[4,5,6, 8], [9,10,11,12],[13,14,15,16]]
  • Asymmetric matrix: [[1,2,3, 4],[4,5,6, 8]]

Want to try solving this problem? https://leetcode.com/problems/spiral-matrix/

Hope you enjoyed this post on traversing a matrix in spiral order. Have a great day!

Posted in Arrays and Strings, Data Structures/ Leetcode

[Problem Solving] Plus one to array

Posted on by Swetha Kannan

Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.

Examples:

  • [1, 2, 3] should return [1, 2, 4]
  • [9, 9] should return [1, 0, 0]

Solution: When we add 1 to a single digit number, there are two outcomes. It can either remain a single digit number or results in 10. If the result is 10, we have to store 0 in the index i and propagate the carry 1 to the previous index i-1.

Let’s traverse the array from the end and add one to the value at index i.

  • If the value becomes 10, store 0 in nums[i] and continue traversing the array
  • Otherwise, add one to the value at nums[i] and return the array

Time Complexity: Since we traverse the array once, O(N)

Space Complexity: No additional space is used, so O(1)

def plusOne(self, digits: List[int]) -> List[int]:
        
        for i in range(len(digits)-1, -1, -1):
            
            if digits[i] + 1 == 10:
                digits[i] = 0
            else:
                digits[i] += 1
                return digits
            
        return [1] + digits #handle the case where all digits become 9

Testing: For most problems it’s good to test the following cases.

  • Empty array: []
  • Single value array: [1]
  • Array with two values: [1, 8]
  • A random array: [1, 2, 3, 4]

In this problem, there are two important cases to test. When the last digit is 9 and when all the digits are 9.

  • [1, 9]
  • [9] or [9, 9] or [9, 9, 9]

Want to try solving this problem? https://leetcode.com/problems/plus-one/

Hope you enjoyed this simple approach to the plus one problem. Have a great day!

Posted in Arrays and Strings, Data Structures/ Leetcode

[Problem Solving] Find Pivot Index

Posted on by Swetha Kannan

Let’s say we are given an array of integers and we want to find a pivot index such that the sum of numbers to the left of this index equals the sum of numbers to the right.

Example: [1, 7, 3, 6, 5, 6]

1 + 7 + 3 = 5 + 6 = 11. In this example, the pivot value is 6, whose array index is 3. If no such index exists, return -1.

Solution #1: To get started with a brute force approach, let’s consider each number as a pivot and calculate the left and right side sums until they equal each other.

Pivot = 1, pivotIndex = 0, leftSum = 0, rightSum = 27

Pivot = 7, pivotIndex = 1, leftSum = 1, rightSum = 20

Pivot = 3, pivotIndex = 2, leftSum = 8, rightSum = 17

Pivot = 6, pivotIndex = 3, leftSum = 11, rightSum = 11. Voila!! Here leftSum = rightSum, so return 3 as the answer.

Time Complexity: A worst case scenario is when we have to traverse the entire array and the pivot index is the last index (n-1) of the array which will be O(N). Calculating left and right side sums adds another O(N) and so it will be an O(N2) algorithm. To improve our algorithm efficiency, we have to try to do this in linear time. In the previous approach, calculation of leftSum added to increased complexity, how can we optimize this part? What if we had access to the leftSum and rightSum values in advance?

Solution #2: Let’s pre-calculate the leftSum and rightSum values for each pivot and store these values in two arrays.

[1, 7, 3, 6, 5, 6]

leftSums = [0, 1, 8, 11, 17, 22, 28]

rightSums = [27, 20, 17, 11, 6, 0]

In leftSums and rightSums, we need to find the index whose values are equal, in this case it’s 11 ie., leftSums[3] = rightSums[3].

Time Complexity: In Solution #2, our time complexity will go down from O(N2) to O(N) since we use pre-calculated sum values to find the pivot index ie., O(N) for pre-calculation plus another O(N) while traversing to find pivot index .

Space Complexity: Using two extra arrays to pre-compute values adds additional 2N space. So the overall space complexity will be O(N).

Code for Solution #2:

def pivotIndex(self, nums: List[int]) -> int:
        
        if not nums:
            return -1
        
        n = len(nums)
        leftSums, rightSums = [0] * n, [0] * n
       
        for i in range(1, n):
            leftSums[i] = leftSums[i-1] + nums[i-1]
            
        for i in range(n-2, -1, -1):
            rightSums[i] = rightSums[i+1] + nums[i+1]
            
        for i in range(n):
            if leftSums[i] == rightSums[i]:
                return i
            
        return -1

Slight improvement on space complexity:

Anytime we are traversing an array both ways and then iterating it all over again, it’s possible to eliminate one of the traversals and calculate values on the fly. In the above code snippet, the following chunks of code are kind of doing the same thing, let’s try to avoid code duplication.

for i in range(1, n):
    leftSums[i] = leftSums[i-1] + nums[i-1]

for i in range(n):
    if leftSums[i] == rightSums[i]:
        return i

We can replace the above two blocks by calculating leftSum on the fly as shown below.

for i in range(0, n):

    if i > 0:
        leftSum += nums[i-1]
    if leftSum == rightSums[i]:
        return i

Time Complexity: O(N)

Space Complexity: O(N)

Testing: For array problems like these, it’s important to test the following cases.

  • Empty array: [] => returns -1
  • Single value array: [1] => returns 0
  • Double value array: [1, 2] => returns -1
  • A random array: [2, 3, 4, 5] => returns 2
  • All given test cases in the problem statement
  • Arrays that have one pivot index: [1, 7, 3, 6, 5, 6] => returns 3
  • Arrays that have more than one pivot index: [1, 0, 1, 0] => returns 0
  • Arrays with no pivot index: [1, 2, 3, 4] => returns -1

Can we do better? Yes!

Solution #3: Introducing prefix sum

If we are given the leftSum of a pivot, what else do I need to get the rightSum? The total sum of the array.

Example: [1, 7, 3, 6, 5, 6]

totalSum = 1 + 7 + 3 + 6 + 5 + 6 = 28

pivot = 7, pivotIndex = 1, leftSum = 1, rightSum = 28 – 1 – 7 = 20

pivot = 6, pivotIndex = 3, leftSum = 11, rightSum = 28 – 11 – 6 = 11

To generalize, rightSum(i) = totalSum – leftSum – nums[i]. Now let’s alter the code accordingly.

def pivotIndex(self, nums: List[int]) -> int:
        
        if not nums:
            return -1
        
        n = len(nums)
        leftSum = 0
        totalSum = sum(nums)
        
        for i in range(n):
            if leftSum == totalSum - leftSum - nums[i]:
                return i
            
            leftSum += nums[i]
            
        return -1

Time Complexity: O(N) for calculation sum of nums, O(N) for finding pivot index, so the overall time complexity will be O(N).

Space Complexity: O(1) since we use constant space to store totalSum and leftSum values.

Want to solve this problem? https://leetcode.com/problems/find-pivot-index/

Hope you enjoyed this step by step approach to iteratively improve upon a solution for a problem. Have a great day!