1 Problem, 24 Programming Languages

A video taking a look at 24 programming language solutions (C, Go, C++, Rust, D, Clojure, Ruby, Elixir, Haskell, Racket, Python, APL, J, BQN, PHP, Scala, Erlang, Typescript, Javascript, Java, Kotlin, Swift, Dart, C#) to one problem.

Contest: 327
Problem Name: Maximum Count of Positive Integer and Negative Integer
Problem Type: Greedy

Chapters:
0:00 Intro
0:31 Problem Description
1:14 Test Cases & Solution Explanation
1:55 Programming Language Solution Categories
2:59 C Solution
3:22 Go Solution
3:35 PHP Solution
4:09 Python Solution
4:25 Dart, Swift & Erlang Solutions
5:00 Javascript & Typescript Solutions
5:17 Clojure & Racket Solutions
5:56 C#, Elixir & Kotlin Solutions
6:20 Scala & Ruby Solutions
6:51 Java & D Solutions
7:14 Haskell Solution
8:15 C++ Solution 1
10:02 C++ Solution 2
10:24 C++ Solution 3
11:03 Rust Solution 1
11:40 Rust Solution 2
11:57 Rust Solution 3
12:19 J, APL & BQN Solutions
12:42 BQN Explanation
17:15 Best Solution Awards
18:15 Performance Comparison
19:05 Outro

[blt_r]

For your first rust solution you could have used `.iter()` instead of `.into_iter()` to not consume the vec, and not clone it. Like this:

fn maximum_count(nums: Vec<i32>) -> i32 {
std::cmp::max(
nums.iter().filter(|&&n| n < 0).count(),
nums.iter().filter(|&&n| n > 0).count(),
) as i32
}

Also in idiomatic rust this function would have taken `&[i32]` and returned `usize`, but I guess there's nothing I can do about it :(

[oj]

The performance difference between C++/C and Rust seems to be C++/C using gcc and rust using a llvm backend, if you use clang for C you get almost the same codegen as rust.

[interested_in_everything]

I really like the code transition effects. Very well produced video.

[hrst]

I would think the solution in C (and similar solutions with a single for loop) could be even faster once you take into account that the numbers are sorted. Start the loop and count the number of negatives. As soon as you encounter a number that is not negative, stop. We now have the number of negative elements. Next up, count the number of zeroes, and stop as soon as you encounter a positive element. The number of positive elements is now simply equal to the total size minus the number of negative elements minus the number of zeroes. So on average, you only have to loop through half of the input array.
Optimized for speed, not for readability/maintainability.

[ubhelbr]

In PHP you probably forgot to put an opening tag in the beginning so the syntax highlighting is correct and your program will simply output its contents :)

[programmingjobesch]

C, PHP, JS, C#, Python, Kotlin and Dart are the best looking/most readable to me for sure.

[vm-seventy]

The array programming languages always fascinate me because of how informationally dense they are! They perform operations that other languages require like 5 lines to describe in just 1 line.

[MegaEnpassant]

Scala has prefix max function: Math.max
Performant Scala code, similar to Rust:

def maximumCount(nums: Array[Int]): Int = {
def op(v: (Int, Int), e: Int) = (if (e > 0) v._1 + 1 else v._1, if (e < 0) v._2 + 1 else v._2)
val (pos, neg) = nums.foldLeft((0, 0))(op)
Math.max(pos, neg)
}

[jesusjar]

The Kotlin solution could be "improved" by using the `it` keyword which is a implicit name for the parameter of a "single-parameter" lambda


so { it < 0 } and { it > 0 } respectively o/

[davidkatz]

Hi Connor, great video as always. Just a note that in D you only need one cast (from result of `max`) because `max` is a template and will return the common type of its two arguments.

[Player_X_YT]

4:14 You're iterating twice through the array, you can do what you did in php or you can do this for a more efficient time:
neg = 0
for i, n in enumerate(nums):
if n<0:
neg += 1
elif n>0:
return max(neg, len(nums)-i)
return neg

[soniablanche]

You have to remember that Big O(n) complexity only matters if the N is big enough, maybe that's why the C++ solution wasn't the fastest, maybe if the array used is large enough you can see the difference.

[roerd]

A bit weird that there's just a single solution that takes advantage of the input data being sorted. All other solutions actually solve a more general problem than what was being described.

binsearch solution in Python:

from bisect import bisect_left, bisect_right
def maximum_count(nums):
a = bisect_left(nums, 0)
b = bisect_right(nums, 0, a)
return max(a, len(nums) - b)

[halneufmille]

3 Julia solutions:
max(sum(nums .> 0), sum(nums .< 0))
max(count(<(0), nums), count(>(0), nums))

To avoid using 0, count or nums more than once:
maximum((count(c(0), nums) for c ∈ (<, >)))

[e]

This video highlights perfectly why I like C: One of the best performance while being trivial to read.


Nice video as always ! I hope to see zig as a contender in the future :)

[terrydaniel]

Here is a fun Julia solution:
If nums is the given vector then sol = max(sum(0 .<nums), sum(0 .>nums))

[dashnone]

with Python you need not put the comprehension into a list and pass it to `len`; you can just sum the comprehension:

def maximumCount(self, nums: List[int]) -> int:
return max(sum(x < 0 for x in nums), sum(x > 0 for x in nums))

[spencerwhite]

Hate to be that guy, but you don't need `.clone()` in the rust solution if you use `.iter()` (by reference) instead of `.into_iter()` (by value). Also, the std library provides a `.partition_point()` method on slices, so you could've done the solution in O(log n) just like the cpp solution.

Also, you could've parallelized the solution because Rust™ guarantees™fearless concurrency™.

[alxjones]

In Kotlin, lambdas with one parameter can use `it` as a default name. So instead of `e -> e < 0`, you can just do `it < 0`.

[FrankieTheKneeMan]

Your comment about excessive duplication on the haskell solution got me thinking, and actually, you can reduce repitition a _lot_ in haskell with some creative use of partition (from Data.List), filter, and uncurry:

maximumCount = uncurry (on max length) . partition (<0) . filter (/=0)

(bonus point-free-ness)

The only thing exactly repeated here is 0, even though there's a bit of "crowding" between partition and filter. There are some ways to maybe get rid of that, but none of the ones I tried really seemed better.