alldroll

// https://leetcode.com/problems/range-sum-query-mutable.go

type NumArray struct {
	tree []int
}

type Range struct {
	index, left, right int
}

alldroll

// https://leetcode.com/problems/sliding-window-maximum
// [3,-1,-1]
// [-1,-1,-15]
// [5,5,5]
// [5,5,3]

// [8,8,8,-1,-1,5,3,6,6]
// [8,3,-3,5,5,5,6,6,-8]
// [8,3,-1,5,5,6,6]

alldroll

// https://leetcode.com/problems/range-sum-query-2d-immutable

type NumMatrix struct {
    sums [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    var sums [][]int
    
    for i := 0; i < len(matrix); i++ {

alldroll

// https://leetcode.com/problems/longest-increasing-subsequence
//
// [10,9,2,5,7,3,7,101,18]
// [a1,...aI-1] - LIS for I-1 elements
// why try to add aI element
// we should observe prev lengths from a1...aI-1 and choose the max length for aJ < aI, where J in [1, I-1]

func lengthOfLIS(nums []int) int {
    lenNums := len(nums)
    

alldroll

// https://leetcode.com/problems/perfect-squares

// 1 -> 1
// 2 -> 1 + 1
// 3 -> (1 + 1) + 1
// 4 -> 4
// 5 -> 4 + 1
// 6 -> 4 + 1 + 1
// 7 -> 4 + 1 + 1 + 1
// 8 -> 4 + 4

alldroll

// https://leetcode.com/problems/knight-probability-in-chessboard

var directions = [8][2]int{
    {-1, -2},
    {-2, -1},
    {-2, 1},
    {-1, 2},
    {1, 2},
    {2, 1},
    {2, -1},

alldroll

// https://leetcode.com/problems/different-ways-to-add-parentheses/

func diffWaysToCompute(input string) []int {
    numbers, operators := parse(input)
    
    return generate(numbers, operators)
}

func generate(numbers []int, operators []rune) []int {
    if len(numbers) < 2 {

alldroll

// https://leetcode.com/problems/serialize-and-deserialize-binary-tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

alldroll

// https://leetcode.com/problems/search-a-2d-matrix-ii

func searchMatrix(matrix [][]int, target int) bool {
    n := len(matrix)
    
    if n == 0 {
        return false
    }
    
    m := len(matrix[0])

alldroll

// https://leetcode.com/problems/product-of-array-except-self

func productExceptSelf(nums []int) []int {
    numsLen := len(nums)
    product := make([]int, numsLen)
    
    product[0] = 1
    
    for i := 1; i < numsLen; i++ {
        product[i] = product[i - 1] * nums[i - 1]