Ruby/dynamic_programming/pascal_triangle_ii.rb at master · TheAlgorithms/Ruby · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
# Given an integer row_index, return the rowIndexth (0-indexed) row of the Pascal's triangle.
# Example 1:
#
# Input: row_index = 3
# Output: [1,3,3,1]
#
# Example 2:
#
# Input: row_index = 0
# Output: [1]
#
# Example 3:
#
# Input: row_index = 1
# Output: [1,1]

#
# Approach 1: Brute Force
#

# Complexity Analysis
#
# Time complexity: O(k^2).
# Space complexity: O(k) + O(k) ~ O(k)

def get_num(row, col)
  return 1 if row == 0 || col == 0 || row == col

  get_num(row - 1, col - 1) + get_num(row - 1, col)
end

def get_row(row_index)
  result = []

  (row_index + 1).times do |i|
    result.push(get_num(row_index, i))
  end

  result
end

row_index = 3
print(get_row(row_index))
# => [1,3,3,1]

row_index = 0
print(get_row(row_index))
# => [1]

row_index = 1
print(get_row(row_index))
# => [1,1]

#
# Approach 2: Dynamic Programming
#

# Complexity Analysis
#
# Time complexity: O(k^2).
# Space complexity: O(k) + O(k) ~ O(k).

# @param {Integer} row_index
# @return {Integer[]}
def get_row(row_index)
  result = generate(row_index)
  result[result.count - 1]
end

def generate(num_rows)
  return [[1]] if num_rows < 1

  result = [[1], [1, 1]]

  (2...num_rows + 1).each do |row|
    prev = result[row - 1]
    current = [1]
    med = prev.count / 2

    (1...prev.count).each do |i|
      current[i] = prev[i - 1] + prev[i]
    end

    current.push(1)
    result.push(current)
  end

  result
end

row_index = 3
print(get_row(row_index))
# => [1,3,3,1]

row_index = 0
print(get_row(row_index))
# => [1]

row_index = 1
print(get_row(row_index))
# => [1,1]

#
# Approach 3: Memory-efficient Dynamic Programming
#

# Complexity Analysis
#
# Time complexity: O(k^2).
# Space complexity: O(k).

# @param {Integer} row_index
# @return {Integer[]}
def get_row(row_index)
  pascal = [[1]]

  (1..row_index).each do |i|
    pascal[i] = []
    pascal[i][0] = pascal[i][i] = 1

    (1...i).each do |j|
      pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
    end
  end

  pascal[row_index]
end

row_index = 3
print(get_row(row_index))
# => [1,3,3,1]

row_index = 0
print(get_row(row_index))
# => [1]

row_index = 1
print(get_row(row_index))
# => [1,1]