interview prep – That Girl Coder

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 November 7, 2022June 23, 2024 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.

Data Structures/ Leetcode

Monotonic Stack

Posted on August 3, 2022 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.

Better Programming, Software Engineering

Learn the basics of Web Caching

Posted on September 22, 2021 by Swetha Kannan

Caching is a mechanism by which responses from the web server such as pages, images etc are stored so that when a client requests the resource again, the response is served from the cache instead of sending a request to the web server.

Why is it important to use caching?

Reduce the number of requests sent to the server
Reduce the latency of responses for the client by serving content from nearby cache instead of a remote server
Reduce network bandwidth by minimizing the number of times a resource is sent over the network from the web server

There are two main types of web caches. Let’s take a look at them.

Browser Cache

If you are a Mac and Chrome user, you can find the the contents of the browser cache in the following path.

/Library/Caches/Google/Chrome/

The browser cache stores parts of pages, files, images etc to help them open faster during a user’s next visit. When a user clicks the back or next button in the browser, the contents are served from the cache directly. The contents of the cache are refreshed regularly after a certain amount of time or during every browser session.

How is the browser cache controlled?

There are several caching headers to define cache policy. Let’s look at the Cache-Control header in the following example which is set to private. This means that a private browser cache can store the response.

There are different caching directives that can be used to set this header.

Caching Headers	Description
Cache-Control: no-store	Nothing should be cached about the request or response
Cache-Control: no-cache	The cache sends a validation request to the server before serving from cache
Cache-Control: private	The response is only applicable to a single user and must not be stored by a shared cache
Cache-Control: public	The response can be stored by any cache
Expires	This header contains the date/time after which the response is considered stale. Ex: Expires: Wed, 22 Sept 2021 12:00:00 GMT
Etag	The entity-tag given in an ETag header field is used for Cache validation. One or more entity-tags, indicating one or more stored responses, can be used in an If-None-Match header by the client for response validation.
Last-Modified	The timestamp given in a Last-Modified header can be used by the client in an If-Modified-Since header field for response validation

Caching Headers

For further reading, please refer to this detailed article on HTTP Caching.

Proxy Cache

Most web services these days use a proxy server as a gateway to handle requests before hitting the web servers. When a server acts as a caching proxy, it stores content and shares those resources with more users. Therefore this type of cache is also known as a shared cache. When a user sends a request, the proxy sever checks for a recent copy of the resource. If it exists, it is then sent back to the user, otherwise the proxy sends a request to the source server and caches the resulting content.

CDNs (Content Delivery Networks) are one of the most popular proxy servers. CDNs are a large network of servers geographically distributed around the world to serve content from a server closest to the user sending a request. When CDNs are configured properly, these can also help a web service prevent DDOS (Distributed Denial of Service) attacks as well.

What is cached?

HTTP caches usually cache responses to a GET request. This can be HTMP documents, images, style sheets or files such as media, javascript files etc. Secure and authenticated requests such as HTTPs will not be cached by shared caches. It is also possible to cache permanent redirects and error responses such as 404 (Not Found).

If the cached content is fresh (not expired or is in accordance with the max-age caching header, then it is served directly from the cache. There are other ways to determine freshness and perform cache validation, but we won’t go into the details here. I encourage you to read up on them if you’re interested.
If the content is stale, the must-revalidate Cache-Control directive is used to tell the cache to verify the freshness of the content.

The primary key used to cache contains the request method (GET) and the target URI (Uniform Resource Identifier). HTTP Caches are limited mostly to GET, so caches mostly ignore other methods and use the URI as the primary caching key.

Caching Best Practices

Consistent URLs – Use the same URL for serving same content on different pages and sites to users.
Library of content – Use a single source of truth library to store images and other shared content such as style sheets etc and refer to the same library from any page or site.
Avoid bulk modifications – The Last-Modified date will be set to a very recent once when you update too many files at the same time, so be aware of changing only the necessary ones.
Cache control – Use the appropriate cache control policies. If the response is private to the user, allow private caching and for generic content, set caching policy to public.
Use caching validators – Use the validation headers we learnt about in the table above such as Etag and Last-Modified so that caches can validate their content without having to download the resources from the server unnecessarily.
Max-age cache control – Set cache control to max-age for pages and images that will be updated only rarely.

I hope you enjoyed learning about the basics of web caching! In the next article, we will learn how to implement a simple cache from scratch.

Data Structures/ Leetcode, June Leetcoding Challenge, Trees

[Problem Solving] Invert a Binary Tree

Posted on June 1, 2020June 23, 2024 by Swetha Kannan

We are given a binary tree as shown below.

Let’s observe the given tree and compare it with the output. What do we notice?

The left child of a node becomes the right child and vice versa. So we start at the root node and invert the left and right children.

     1
   /   \
  2     3

becomes

     1
   /   \
  3     2

We then invert the left and right sub-trees starting at each of those children. This leads to a naturally recursive approach.

     1
   /   \
  3     2
 / \   / \
6   7 4   5

becomes

     1
   /   \
  3     2
 / \   / \
7   6 5   4

An intuitive way to solve most tree problems is to use recursion. Now we have to decide a few things before coding.

Base case:

Here, the base case would be a NULL node. We simply return at that point since there are no nodes left to invert.

Recursive strategy:

Our recursive strategy involves the following steps.

Invert the left and right child of current node
Recursive call to invert the left sub-tree starting at the left child
Recursive call to invert the right sub-tree starting at the right child

Time Complexity: We will end up visiting each node in the tree, so the time complexity will be O(N) where N is the number of nodes in the tree.

Space Complexity: In recursion problems, an internal stack is used to temporarily hold elements, so the space complexity will be O(H) where H is the height of the tree. This is because as we recurse over left and right sub-trees, the function calls will go as deep as the tree height. In the worst case, H -> N, so the overall space complexity will be O(N) where N is the number of nodes in the tree.

Code for the above solution:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invertTree(self, root: TreeNode) -> TreeNode:

    def invertTreeHelper(root):

        if not root:
            return

        root.left, root.right = root.right, root.left
        invertTreeHelper(root.left)
        invertTreeHelper(root.right)

    invertTreeHelper(root)
    return root

Testing:

These are some of the cases that are good to test for tree problems.

Given test case: [1,2,3,4,5,6,7]
Empty tree: []
No children: [1]
No right child: [1, 2]
Right skewed tree: [1,null,2,null,3,null,4,null,5,null,6,null,7]
Left skewed tree: [1,2,null,3,null,4,null,5,null,6,null,7]

Want to try to solve this problem? https://leetcode.com/problems/invert-binary-tree/

Hope you learnt how to invert a binary tree. Have a great day!

Arrays and Strings, Data Structures/ Leetcode

[Problem Solving] Spiral Matrix

Posted on May 27, 2020June 23, 2024 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.

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.

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!

Arrays and Strings, Data Structures/ Leetcode, Matrix problems

[Problem Solving] Diagonal Traverse

Posted on May 25, 2020June 23, 2024 by Swetha Kannan

Given a matrix of M x N elements, return the elements in diagonal order as shown below.

[
 [ 1, 2, 3, 4 ],
 [ 5, 6, 7, 8 ],
 [ 9, 10, 11, 12 ],
 [13, 14, 15, 16 ]
]

Output: [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15, 16]

Solution #1: To begin with, let’s ignore the part where alternate diagonal elements need to be reversed. Let’s try to traverse the matrix as shown above in image 2.

We see that a diagonal always starts either from the top row or the last column of elements. If we are given the starting point of a diagonal, how can we get to the next diagonal element?

For example, let’s say we are at 4 which is at (r = 0, c = 3) where r and c indicate the row and column indexes respectively. To get to the next element, we have to move one row down and one column to the left, ie., r = 1, c = 2. To generalize:

next_r = r + 1, next_c = c – 1

To match the expected results where alternate diagonal elements are reversed in order, we can collect the diagonal elements and reverse the order of alternate diagonals before adding to the results. The code below is an intuitive way of solving this problem.

def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        results = []
        row, col = 0, 0
        
        while row < m and col < n:
            
            temp = []
            
            # To collect all elements of a diagonal, keep going one row down and column 
            # to the left until we hit matrix boundaries
            i, j = row, col
            while i < m and j >= 0:
                temp.append(matrix[i][j])
                i += 1
                j -= 1
                
            # Reverse the order for alternate diagonals
            if (row + col) % 2 == 0:
                results.extend(temp[::-1])
            else:
                results.extend(temp)
                
            # Set row, col to traverse the next diagonal
            if col < n - 1:
                col += 1
            else:
                row += 1
                
        return results

Time Complexity: O(M*N) where M is the number of rows and N is the number of columns in the matrix

Space Complexity: The additional space used in this solution is the temp array which holds the diagonal elements. The largest diagonal of a matrix has min(M, N) elements, so space complexity is O(min(M, N)).

Testing: When it comes to matrix problems, make sure to test the following cases.

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]]

Solution #2: The above solution is perfectly acceptable. If you notice the indices of diagonal elements, they all sum to the same number. Remember this pattern as it might come handy while manipulating diagonal elements of a matrix.

Keeping this in mind, here is an alternate solution to this problem where we use the sum of indices as keys in a dictionary to store values belonging to a particular diagonal.

import collections

def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        elements = collections.defaultdict(list)
        results = []
    
        for i in range(m):
            for j in range(n):
                elements[i+j].append(matrix[i][j])
                
        for k, v in elements.items():
            if k % 2 == 0:
                results.extend(v[::-1])
            else:
                results.extend(v)

        return results

Time Complexity: O(M*N)

Space Complexity: O(M*N)

Want to try solving this problem? https://leetcode.com/problems/diagonal-traverse/

Hope you enjoyed solving the diagonal traverse problem. Have a great day!

Arrays and Strings, Data Structures/ Leetcode

[Problem Solving] Plus one to array

Posted on May 23, 2020June 23, 2024 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!

Arrays and Strings, Data Structures/ Leetcode

[Problem Solving] Find Pivot Index

Posted on May 23, 2020June 23, 2024 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(N²) 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(N²) 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!