java – Largest Sum Contiguous Subarray – Kadene’s algorithm

I am looking forward to an answer to improve this code?

Thanks.

Test class

package test;

import main.algorithms.LargestSumContiguousSubarray;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class LargestSumContiguousSubarrayTest {

    LargestSumContiguousSubarray largestSumContiguousSubarray;

    @Before
    public void setUp(){
        largestSumContiguousSubarray = new LargestSumContiguousSubarray();
    }

    @Test
    public void testSumContiguousSubArray(){
        int() a = {-2, -3, 4 - 1, -2, 1, 5, -3};
        int sum = 7;
        Assert.assertEquals(sum, largestSumContiguousSubarray.kadenesAlgo(a));
    }

}

LargestSumContiguousSubarray.java class

package main.algorithms;

public class LargestSumContiguousSubarray {

    // O(n)
    // Kadene's algorithm
    public int kadenesAlgo(int() a) {

        // This is also works for negative numbers
        int max_so_far = a(0);
        int curr_max = a(0);

        for(int i=0;i<a.length; i++){
            curr_max = Math.max(a(i), curr_max+a(i));
            max_so_far = Math.max(max_so_far, curr_max);
        }
        return max_so_far;
    }
}

arrays – Largest subarray with sum greater than K

I was trying to understand the code of [https://www.geeksforgeeks.org/largest-subarray-having-sum-greater-than-k/amp/]
but could not understand.

Specifically, I did not understand the following

1.what does minInd array hold?

2.What is the use of minInd in keeping track of largest subarray?

3.What does find method return?

Illustration with an example would be highly appreciated.

c++ – LeetCode 862: Shortest Subarray with Sum at Least K

I’m posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

Problem

  • Return the length of the shortest, non-empty, contiguous subarray of nums with sum at least k.
  • If there is no non-empty subarray with sum at least k, return -1.

Example 1:

Input: nums = (1), k = 1 Output: 1

Example 2:

Input: nums = (1,2), k = 4 Output: -1

Example 3:

Input: nums = (2,-1,2), k = 3 Output: 3

Note:

  • $1 <= nums.length <= 50000$
  • $-10 ^ 5 <= nums(i) <= 10 ^ 5$
  • $1 <= k <= 10 ^ 9$

Code

#include <vector>
#include <algorithm>
#include <deque>

class Solution {
public:
    static int shortestSubarray(std::vector<int> nums, const int k) {
        const int length = nums.size();
        int shortest = length + 1;

        std::deque<int> deque_indicies;

        for (int index = 0; index < length; index++) {
            if (index) {
                nums(index) += nums(index - 1);
            }

            if (nums(index) >= k) {
                shortest = std::min(shortest, index + 1);
            }

            while (!deque_indicies.empty() && nums(index) - nums(deque_indicies.front()) >= k) {
                shortest = std::min(shortest, index - deque_indicies.front());
                deque_indicies.pop_front();
            }

            while (!deque_indicies.empty() && nums(index) <= nums(deque_indicies.back())) {
                deque_indicies.pop_back();
            }

            deque_indicies.emplace_back(index);
        }

        return shortest <= length ? shortest : -1;
    }
};

algorithms – Smallest subarray problem

In my answer I will assume that all numbers are at most $M$ big, i.e. $A(i) le M$.

First some comments about your both approaches.

Computing the GCD takes $O(log M)$ time. So your first approach is actually $O(N^2 log M)$.
I also don’t think that your second approach is actually better than $O(N^2)$. For instance assume if all the numbers of the first half of the array are equal. Then for each of those numbers you have at least $Theta(N)$ effort for each divisor of $N$. Which means that the complexity for such a test case is something like $O(N^2 sqrt M)$.


Let’s first discuss a very trivial (but slower) dynamic programming solution, on which I will later base a better one.

Let’s define the function $f$ as $f(i)$ is the smallest number of subarrays in which you can split the prefix of size $i$ of the array (the first $i$ numbers). Also let $f(i) := infty$ if it is not possible to split the array, and $f(0) := 0$.

It’s easy to see, that you can compute $f(i)$ using the recursion:

$$f(i) = min_{substack{1 le j le i\ gcd(A(i), A(j)) > 1}} f(j-1) + 1$$

This formula is very trivially to implement together with dynamic programming, and will have the complexity $O(N^2 log M)$.

f(0) = 0
for i = 1 to N:
    f(i) = infinity
    for j = 1 to i:
        if gcd(A(i), A(j)) > 1:
            f(i) = min(f(i), f(j-1)) + 1
print f(N)

Now to a better approach. We need two mathematical facts that will help us:

  • If two numbers have a common divisor greater than one, then they have a common prime factor.
  • A number $le M$ has at most $log M$ prime factors.

Let the set of prime factors of $x$ be $P(x)$.

Then we can also rewrite the recursion for $f$ as:

$$f(i) = min_{p in P(A(i))} left( min_{substack{1 le j le i\ p ~|~ A(j)}} f(j-1) right) + 1$$
In other word, if $A(i) = 20 = 2^2 cdot 5$, then we look for all previous numbers who are divisible by 2, and take the minimum of $f(j-1)$, and for all previous numbers who are divisible by $5$ and take the minimum of $f(j-1)$. The actual optimal value $f(i)$ will one more than the minimum of both.

If we define $g(p, i)$ as the minimum of $f(j-1)$ with $p ~|~ A(j)$ and $1 le j le i$, then the formula simplifies to:

$$f(i) = min_{p in P(A(i))} g(p, i) + 1$$

We can actually apply some sort of dynamic programming also to the function $g$.
We store the values in a hash table.
First we initialize the function for every possible prime factor with $g(p) = infty$, and whenever a $f(j-1)$ changes, we update $g(p)$ for every $p in P(A(j))$.

This means, after we update $f(i)$, we only need to update $O(log M)$ different values of $g$.

This gives us the following algorithm:

# initialize g
for all p:
    g(p) = infinity

# set the first value f(0)
f(0) = 0
# update g
for p in P(A(1)):
    g(p) = min(g(p), f(0))

for i = 1 to N:
    # first compute f(i)
    f(i) = infinity
    for p in P(A(i)):
        f(i) = min(f(i), g(p)) + 1

    # and then update g
    if i < N:
        for p in P(A(i+1)):
            g(p) = min(g(p), f(i))
print f(N)

It’s easy to see that this algorithm runs in $O(N log M)$ time.

A shorter variation, but with the exact same approach and complexity, would also be:

for all p:
    g(p) = infinity
f(0) = 0
for i = 1 to N:
    f(i) = infinity
    for p in P(A(i)):
        g(p) = min(g(p), f(i-1))
        f(i) = min(f(i), g(p)) + 1
print f(N)

The only thing to discuss is, how we get the prime factorization of each number.
There are loads of different approaches.
For instance if $M$ is not too big, you can compute the Sieve of Eratosthenes in $O(M log M)$ and during the computation store a prime factor for each number $le M$. This allows to compute the prime factorization of each number in $O(log M)$.
Another option would be just to compute the prime factors on the fly, which would give take additionally $O(N sqrt{M}$) time if you use the typical trial division until square root algorithm.

python – Optimize function that returns length of a subarray

I did an exercise today on where the task is to write a function that returns the length of the longest subarray where the difference between the smallest and biggest value in the subarray is no more than 1. I had a solution that works but it’s too slow to pass the tests that have big arrays. What is it about my solution that makes it very slow with huge arrays?

def longestSubarray(arr):
    longest = 0
    arr_len = len(arr)
    for i in range(arr_len):
        for j in range(i, arr_len):
            sub = arr(i: j+1)
            if max(sub) - min(sub) > 1:
                continue
            length = len(sub)
            if length > longest:
                longest = length
    return longest

algorithms – Cannot understand the relevance of $binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem

I recently came across the sentence in the Book Introduction to Algorithms section 4.1 The maximum sub-array problem:

We still need to check $binom{n-1}{2} = Theta(n^2)$ subarrays for a period of $n$ days.

Here $n$ is the number of days taken as an example to show the changes in price of stock.

We can consider this is the size of an array A.

Where we are provided with an Array A and we need to find the net change is maximum from the first day to the last day.

To explain more specifically it means for an array $A$ of size $n$ we need to check $binom{n-1}{2}$ subarrays.

But, I cannot understand how we need $binom{n-1}{2}$ sub-arrays?

If we take an array of size 5 could someone please explain to me why we need only 6 sub-arrays.
Won’t the sub-arrays be:

(1...5)
(1...4)
(1...3)
(1...2)

(2...4)
(2...5)


(3...5)
(4...5)

Please correct me if I am wrong.
References: Maximum Subarray Problem

The Maximum Sub-array problem
Thank you.

LeetCode 560: Subarray Sum Equals K [C++/Java]

According to LeetCode, the following question is one of the most frequent interview questions asked by companies such as Facebook and Google. Here, I’m posting C++/Java codes, if you’d like to review, please do so.

Thank you!

Given an array of integers and an integer target (K), you need to find the
total number of continuous subarrays whose sum equals to target.

Example 1:

Input:nums = (1,1,1), target = 2 Output: 2

Constraints:

The length of the array is in range (1, 20,000).
The range of numbers in the array is (-1000, 1000) and the range of the integer target is (-1e7,
1e7).

C++

class Solution {
public:
    int subarraySum(vector<int> &nums, int target) {
        map<int, int> prefix_sum;
        int sum = 0, subarrays = 0;
        prefix_sum(0)++;
        for (int index = 0; index < nums.size(); index++) {
            sum += nums(index);
            subarrays += prefix_sum(sum - target);
            prefix_sum(sum)++;
        }

        return subarrays;
    }
};

Java

class Solution {
    public int subarraySum(int() nums, int target) {
        int sum = 0, subarrays = 0;
        Map<Integer, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0, 1);

        for (int index = 0; index != nums.length; index++) {
            sum += nums(index);

            if (prefixSum.get(sum - target) != null)
                subarrays += prefixSum.get(sum - target);

            prefixSum.put(sum, -~prefixSum.getOrDefault(sum, 0));
        }

        return subarrays;
    }
}

Reference

beginner – LeetCode 560: Subarray Sum Equals K [Python]

According to LeetCode, the following question is one of the most frequent interview questions asked by companies such as Facebook and Google. In this post, I’m adding Python solution, if you’d like to review, please do so.

Thank you!

Given an array of integers and an integer target (K), you need to find the
total number of continuous subarrays whose sum equals to target.

Example 1:

Input:nums = (1,1,1), target = 2 Output: 2

Constraints:

The length of the array is in range (1, 20,000).
The range of numbers in the array is (-1000, 1000) and the range of the integer target is (-1e7,
1e7).

Python


from typing import List


class Solution:
    def subarraySum(self, nums: List(int), target: int) -> int:
        subarrays = 0
        cur_sum = 0
        memo = {0: 1}
        for index, num in enumerate(nums):
            cur_sum += num
            subarrays += memo.get(cur_sum - target, 0)
            memo(cur_sum) = -~memo.get(cur_sum, 0)
        return subarrays

Reference

java – Print SubArray of Maximum Contiguous product in Array

Maximum Product Subarray
Given an array that contains both positive and negative integers, find the subarray of the maximum product .
Examples:

Input: arr[] = {6, -3, -10, 0, 2}
Output: The subarray is {6, -3, -10}

Input: arr[] = {-1, -3, -10, 0, 60}
Output: The subarray is {60}

Input: arr[] = {-2, -3, 0, -2, -40}
Output: The subarray is {-2, -40}

algorithms – Maximum Circular Subarray sum

This is a question from the book Algorithms by Jeff Erickson.

Suppose A is a circular array. In this setting, a “contiguous subarray” can be either an interval A(i .. j) or a suffix followed by a prefix A(i .. n) · A(1 .. j). Describe and analyze an algorithm that finds a contiguous subarray of A with the largest sum.
The input array consists of real numbers.

My approach:

There are two possibilities

1.) No Wrapping around (We can use Kadane’s Algorithm)

2.) Wrapping around(ie; Starting index of the subarray is greater than the ending index) (I have doubt in this case)

Now return the maximum of two cases as result.

For the second case, searching on the internet provided an approach without proof.

The approach is to find the subarray with minimum sum and subtract it from the sum of the entire array (ie; sum(A) – min_subarray_sum(A)). How is this solution correct?

Link for the method used in the second case: https://www.geeksforgeeks.org/maximum-contiguous-circular-sum/