◐ Shell
reader mode source ↗
Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
File filter
Conversations
Jump to
Diff view
Apply and reload
Show whitespace
Diff view
Apply and reload
4 changes: 2 additions & 2 deletions 1-js/05-data-types/04-array/1-item-value/solution.md
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
The result is `4`:


```js run
Expand All @@ -13,5 +13,5 @@ alert( fruits.length ); // 4
*/!*
```

That's because arrays are objects. So both `shoppingCart` and `fruits` are the references to the same array.

8 changes: 4 additions & 4 deletions 1-js/05-data-types/04-array/1-item-value/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,18 +2,18 @@ importance: 3

---

# Is array copied?

What is this code going to show?

```js
let fruits = ["Apples", "Pear", "Orange"];

// push a new value into the "copy"
let shoppingCart = fruits;
shoppingCart.push("Banana");

// what's in fruits?
alert( fruits.length ); // ?
```

44 changes: 22 additions & 22 deletions 1-js/05-data-types/04-array/10-maximal-subarray/solution.md
Original file line number Diff line number Diff line change
@@ -1,43 +1,43 @@
# The slow solution

We can calculate all possible subsums.

The simplest way is to take every element and calculate sums of all subarrays starting from it.

For instance, for `[-1, 2, 3, -9, 11]`:

```js no-beautify
// Starting from -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// Starting from 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// Starting from 3:
3
3 + (-9)
3 + (-9) + 11

// Starting from -9
-9
-9 + 11

// Starting from -11
-11
```

The code is actually a nested loop: the external loop over array elements, and the internal counts subsums starting with the current element.

```js run
function getMaxSubSum(arr) {
let maxSum = 0; // if we take no elements, zero will be returned

for (let i = 0; i < arr.length; i++) {
let sumFixedStart = 0;
Expand All @@ -57,25 +57,25 @@ alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
```

The solution has a time complexity of [O(n<sup>2</sup>)](https://en.wikipedia.org/wiki/Big_O_notation). In other words, if we increase the array size 2 times, the algorithm will work 4 times longer.

For big arrays (1000, 10000 or more items) such algorithms can lead to a serious sluggishness.

# Fast solution

Let's walk the array and keep the current partial sum of elements in the variable `s`. If `s` becomes negative at some point, then assign `s=0`. The maximum of all such `s` will be the answer.

If the description is too vague, please see the code, it's short enough:

```js run
function getMaxSubSum(arr) {
let maxSum = 0;
let partialSum = 0;

for (let item of arr) { // for each item of arr
partialSum += item; // add it to partialSum
maxSum = Math.max(maxSum, partialSum); // remember the maximum
if (partialSum < 0) partialSum = 0; // zero if negative
}

return maxSum;
Expand All @@ -89,6 +89,6 @@ alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0
```

The algorithm requires exactly 1 array pass, so the time complexity is O(n).

You can find more detail information about the algorithm here: [Maximum subarray problem](http://en.wikipedia.org/wiki/Maximum_subarray_problem). If it's still not obvious why that works, then please trace the algorithm on the examples above, see how it works, that's better than any words.
18 changes: 9 additions & 9 deletions 1-js/05-data-types/04-array/10-maximal-subarray/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,29 +2,29 @@ importance: 2

---

# A maximal subarray

The input is an array of numbers, e.g. `arr = [1, -2, 3, 4, -9, 6]`.

The task is: find the contiguous subarray of `arr` with the maximal sum of items.

Write the function `getMaxSubSum(arr)` that will return that sum.

For instance:

```js
getMaxSubSum([-1, *!*2, 3*/!*, -9]) == 5 (the sum of highlighted items)
getMaxSubSum([*!*2, -1, 2, 3*/!*, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, *!*11*/!*]) == 11
getMaxSubSum([-2, -1, *!*1, 2*/!*]) == 3
getMaxSubSum([*!*100*/!*, -9, 2, -3, 5]) == 100
getMaxSubSum([*!*1, 2, 3*/!*]) == 6 (take all)
```

If all items are negative, it means that we take none (the subarray is empty), so the sum is zero:

```js
getMaxSubSum([-1, -2, -3]) = 0
```

Please try to think of a fast solution: [O(n<sup>2</sup>)](https://en.wikipedia.org/wiki/Big_O_notation) or even O(n) if you can.
16 changes: 8 additions & 8 deletions 1-js/05-data-types/04-array/2-create-array/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,17 +2,17 @@ importance: 5

---

# Array operations.

Let's try 5 array operations.

1. Create an array `styles` with items "Jazz" and "Blues".
2. Append "Rock-n-Roll" to the end.
3. Replace the value in the middle by "Classics". Your code for finding the middle value should work for any arrays with odd length.
4. Strip off the first value of the array and show it.
5. Prepend `Rap` and `Reggae` to the array.

The array in the process:

```js no-beautify
Jazz, Blues
Expand Down
7 changes: 3 additions & 4 deletions 1-js/05-data-types/04-array/3-call-array-this/solution.md
Original file line number Diff line number Diff line change
@@ -1,6 +1,6 @@
The call `arr[2]()` is syntactically the good old `obj[method]()`, in the role of `obj` we have `arr`, and in the role of `method` we have `2`.

So we have a call of the function `arr[2]` as an object method. Naturally, it receives `this` referencing the object `arr` and outputs the array:

```js run
let arr = ["a", "b"];
Expand All @@ -11,5 +11,4 @@ arr.push(function() {

arr[2](); // a,b,function(){...}
```

The array has 3 values: initially it had two, plus the function.
7 changes: 3 additions & 4 deletions 1-js/05-data-types/04-array/5-array-input-sum/solution.md
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
Please note the subtle, but important detail of the solution. We don't convert `value` to number instantly after `prompt`, because after `value = +value` we would not be able to tell an empty string (stop sign) from the zero (valid number). We do it later instead.


```js run demo
Expand All @@ -8,9 +8,9 @@ function sumInput() {

while (true) {

let value = prompt("A number please?", 0);

// should we cancel?
if (value === "" || value === null || !isFinite(value)) break;

numbers.push(+value);
Expand All @@ -25,4 +25,3 @@ function sumInput() {

alert( sumInput() );
```

14 changes: 7 additions & 7 deletions 1-js/05-data-types/04-array/5-array-input-sum/task.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,14 +2,14 @@ importance: 4

---

# Sum input numbers

Write the function `sumInput()` that:

- Asks the user for values using `prompt` and stores the values in the array.
- Finishes asking when the user enters a non-numeric value, an empty string, or presses "Cancel".
- Calculates and returns the sum of array items.

P.S. A zero `0` is a valid number, please don't stop the input on zero.

[demo]
Loading
Toggle all file notes Toggle all file annotations