HackerRank Max Transform Python Solution

Question

I am trying to solve this question on HackerRank (problem details below).

Naive solution

This solution implements the problem as described and produces the correct solution. It is not very efficient, however, and produces time-out errors on the predefined tests for larger sized arrays of A, e.g. big_A (see below).

big_A = [371, 7372, 5149, 3766, 587, 3575, 799, 7431, 8071, 6041, 6332, 9656, 3128, 6271, 6708, 7741, 8412, 9687, 6014, 4012, 6124, 415, 5356, 3053, 2810, 9803, 9978, 7697, 70, 966242, 4976, 8644, 3429, 8476, 4383, 5373, 251, 9021, 1645, 8793, 7913, 5763, 3178, 9554, 6988, 1701, 6574, 7263, 1487, 9215, 3403, 2624, 8997, 123929, 4557, 3036, 9485, 546, 4085, 627, 22122, 365, 6823, 8838, 8475, 693102, 4140, 204801, 6701, 4831, 4312, 6549, 8092, 9138, 8040, 8121, 3325, 27206, 343, 5881, 44268, 7494, 283, 5452, 7417, 3473, 1788, 183, 4904, 8625, 3536, 3142, 4263, 99129, 9012, 1136, 3980, 3626, 9915, 7515, 77976, 2309, 694, 62514, 6651, 6503, 7004, 7591, 7775, 9187, 73133, 5078, 3353, 674195, 246, 693102, 6918, 29866, 5033, 4831, 4365, 5106, 7457, 4719, 7242, 8838, 1593, 7303, 4295, 5333, 2027, 4717, 8930, 6011, 1528, 959, 14383, 7291, 2910, 8407, 3492, 9187, 28684, 8153, 7990, 1580, 8818, 378, 2010, 3425, 4415, 4786, 3550, 716, 2866, 157, 8526, 3913, 7869, 3171, 5241, 5733, 7276, 1115, 85705, 6616, 992977, 7060, 6922, 7492, 6988, 1216, 2082, 3429, 1082, 8818, 430, 6509, 7837, 81, 8493, 106, 1538, 5173, 6420, 307421, 1843, 5413, 5356, 9176, 8109, 2973, 9445, 7080, 5884, 65602, 3259, 1565, 1472, 9060, 6545, 4969, 2516, 6288, 273932, 8096, 6901, 7482, 5380, 29866, 754, 3586, 8765, 1465, 152208, 572, 83558, 2506, 935206, 9450, 543753, 4228, 4910, 8167, 51337, 8048, 7967, 6042, 8110, 8148, 4184, 5023, 4184, 5575, 1854, 4307, 14503, 6535, 4257, 5047, 3806, 2871, 2880, 5829, 3159, 53682, 9186, 3628, 3578, 6497, 90013, 364, 9922, 2923, 9534, 8672, 2116, 2742, 2685, 2887, 5941, 1496, 1984, 5661, 5401, 2733, 2840, 8659, 1340, 3844, 2576, 9534, 7778, 4, 15811, 4295, 8765, 6107, 7008, 1729, 6591, 8342, 8460, 14431, 8297, 8526, 7449, 4029, 4897, 3017, 5505, 235, 3712, 4199, 6104, 4456, 8741, 3642, 8004, 6613, 9917, 96502, 2024, 7696, 6954, 962, 3961, 8771, 397537, 8524, 8030, 933, 3117, 3879, 3256, 5661, 8544, 9275, 74765, 9281, 4916, 5682, 3456, 5066, 6436, 4379, 85739, 280, 4624, 4161, 5809, 380, 32154, 7855, 5088, 2834, 9437, 3523, 5472, 8778, 2405, 22859, 5779, 6324, 7080, 22387, 6089, 7472, 3862, 5314, 36091, 1532, 3829, 19743, 2986, 4334, 4626, 9283, 4322, 1322, 2775, 5763, 8457, 85705, 6838, 8101, 8793, 7763, 3562, 8709, 6643, 8631, 4459, 5005, 8357, 33690, 9400, 8779, 2736, 3839, 8200, 5947, 3155, 20111, 6432, 1286, 4937, 1424, 2910, 2625, 7367, 6116, 7373, 234, 6773, 8242, 8647, 6378, 7488, 78555, 1603, 4759, 6448, 8798, 44, 4042, 6586, 9400, 266, 2454, 90742, 3712, 5683, 7705, 7821, 4134, 2066, 978, 6121, 7841, 5809, 6463, 4048, 6761, 9850, 29866, 4591, 5848, 6343, 61, 6346, 6110, 2980, 2581, 3524, 3113, 5710, 5130, 39480, 425, 8502, 1943, 7602, 3523, 1136, 69974, 2090, 4922, 616, 2124, 42110, 6195, 1141, 9817, 3616, 813, 4743, 9048, 6681, 415, 8757, 9136, 8178, 9160, 63943, 9963, 6413, 170, 30849, 3115, 7750, 4154, 1626, 9524, 5700, 3150, 2280, 6816, 6561, 55836, 82526, 2161, 5503, 7026, 6685, 592471, 4675, 4558, 2138, 3348, 9428, 916, 5556, 1508, 3876, 4694, 8905, 4718, 1866, 5777, 6474, 7957, 9540, 6006, 6452, 4491, 2371, 4461, 2168, 2813, 3528, 9721, 9687, 66271, 1043, 8079, 4709, 6858, 6781, 2416, 1113, 433780, 8520, 686044, 8358, 7485, 6573, 3504, 45587, 1843, 7779, 2421, 5909, 3817, 73133, 22213, 8108, 5475, 77, 7088, 1752, 9496, 7332, 48517, 101, 7555, 4129, 4166, 1267, 7053, 2521, 8520, 1461, 3159, 3591, 9013, 1598, 10954, 8932, 3248, 6110, 7588, 3269, 8968, 894344, 84763, 174, 4166, 630, 9163, 4512, 99378, 81001, 364, 2433, 2690, 1531, 7737, 3112, 44, 9687, 5472, 7329, 5273, 9973, 29810, 189, 7088, 3552, 992977, 5988, 4046, 1464, 5333, 6118, 8243, 5604, 5434, 4743, 8089, 2491, 2083, 8410, 8976, 7449, 977, 47720, 5020, 6838, 190, 5763, 5041, 33460, 3355, 587, 6867, 6824, 9522, 6485, 4899, 6444, 3258, 9454, 1401, 3861, 1668, 6593, 2699, 33, 4485, 2186, 314, 5579, 4747, 1881, 9140, 7695, 3281, 5967, 5982, 5467, 8189, 8345, 1928, 8449, 6375, 20111, 3317, 5036, 2299, 3376, 9646, 3097, 977, 258395, 5739, 5345, 2728, 9356, 5436, 397537, 7810, 4447, 4334, 1999, 1045, 71835, 4403, 1752, 90742, 3842, 5378, 7453, 2456, 628, 5432, 6701, 6807, 7977, 7645, 8818, 1714, 8342, 44654, 8177, 744, 9483, 8568, 6806, 260, 4725, 3735, 5102, 2922, 7837, 686044, 2667, 6937, 15811, 4292, 4446, 9626, 6914, 779, 1324, 8517, 2426, 7251, 93108, 9435, 4235, 16143, 7208, 7303, 1598, 4419, 14503, 6191, 2979, 4216, 757, 5921, 961071, 1955, 6758, 8999, 9024, 9985, 65810, 572, 4620, 4489, 4627, 8378, 8567, 5726, 5525, 6998, 4365, 39649, 4297, 21762, 5855, 27206, 7364, 3159, 6747, 2041, 7400, 5081, 9024, 177415, 9413, 6409, 97508, 621, 85545, 9907, 8192, 6280, 9934, 1574, 3626, 227, 84763, 21762, 837, 9022, 3552, 1053, 89162, 4840, 6089, 1121, 7878, 1255, 5229, 2721, 9510, 5103, 4854, 6968, 9496, 866, 5856, 3107, 7000, 5106, 390, 3737, 3469, 8721, 1866, 6081, 4604, 33442, 861368, 7848, 9893, 1627, 6104, 3891, 8359, 7716, 1000, 5090, 5828, 7173, 9317, 2611, 6605, 6311, 7553, 6271, 8051, 751, 5191, 6110, 9746, 921183, 4680, 183391, 1078, 5575, 73660, 9702, 5025, 4242, 1929, 3069, 4426, 1098, 1716, 6340, 2258, 7683, 3097, 9708, 6536, 5387, 40277, 8480, 1479, 8897, 22213, 4860, 1755, 5321, 2622, 8995, 2454, 7418, 7001, 6020, 58942, 809, 7681, 244, 1814, 6564, 9875, 7450, 9982, 5260, 2148, 8203, 7357, 6685, 7618, 531, 8872, 85765, 7766, 9115, 6852, 644315, 1388, 3645, 4438, 6409, 912, 5892, 20289, 7058, 6559, 5760, 6953, 328, 5108, 2310, 2589, 2321, 8768, 5853, 43602, 3353, 68378, 19, 66, 1439, 3765, 40, 20289, 5575, 1974, 5687, 5517, 88489, 7917, 5226, 171, 2685, 7219, 9711, 6936, 6523, 9945, 5510, 9654, 5894, 8344, 6131, 243, 1982, 9723, 4244, 11284, 4409, 1597, 2506, 160, 2060, 1779, 467, 2532, 2733, 4065, 5235, 8049, 9795, 9704, 8030, 4973, 5452, 6021, 2402, 8313, 919, 5366, 4044, 5654, 9460, 1892, 8935, 99378, 4592, 4101, 4066, 121, 2887, 63310, 2313, 5349, 6287, 7674, 1196, 7091, 53301, 6308, 4461, 1536, 2481, 6022, 9721, 6123, 7001, 4071, 4444, 6574, 6867, 5188, 8931, 5666, 4910, 6819, 8556, 6781, 3484, 2243, 8344, 8778, 6664, 5829, 7332, 51760, 9074, 7489, 9812, 8917, 2936, 2409, 6360, 7104, 9758, 6026, 2061, 6424, 4064, 9528, 4951, 43278, 5695, 3918, 51337, 7291, 8779, 3645, 67977, 7620, 218520, 10985, 65636, 9149, 2138, 439533, 199, 8778, 2917, 15850, 1668, 3444, 5205, 9746, 9286, 8432, 4282, 2728, 745, 7373, 2251, 2573, 2085, 581, 9530, 1772, 9563, 3346, 12708, 9411, 53301, 6796, 2535, 2527, 4542, 3399, 3766, 317, 5107, 4761, 5666, 3206, 4016, 9309, 4835, 7209, 5985, 2871, 10985, 695, 1879, 8729, 7329, 1668, 451, 4352, 1074, 9997, 1987, 1021, 2402, 5010, 9775, 15850, 3525, 485, 5821, 67551, 90227, 5850, 6480, 8344, 4446, 2695, 419, 4725, 2978, 7860, 7364, 3483, 2612, 7840, 9830, 6847, 965, 5534, 2540, 7896, 7278, 9832, 5650, 4182, 2894, 9437, 6108, 7143, 8957, 3732, 9714, 4476, 4890, 9907, 1822, 4890, 8920, 572, 5091, 7260, 9759, 8412, 7995, 433535, 3525, 1622, 9969, 8917, 3574, 5132, 2387, 9212, 7018, 6186, 1744, 4835, 9013, 9311, 6820, 5298, 4281, 6123, 6291, 433780, 63310, 69974, 919, 5238, 6051, 5204, 9982, 7446, 3932, 31807, 3190, 77976, 9809, 7332, 1391, 609007, 1900, 9935, 7943, 1798, 11553, 8747, 6288, 29866, 2744, 3792, 2260, 5747, 4510, 5041, 4929, 3162, 69881, 5988, 6222, 1880, 2794, 6537, 8980, 5848, 1517, 1251, 2581, 14289, 9726, 2143, 294, 9367, 3015, 7058, 2835, 3646, 99129, 69974, 2114, 15811, 2480, 2576, 6015, 944, 7391, 9203, 883, 5338, 88907, 2402, 6793, 7213, 9512, 5033, 7491, 7496, 4665, 6409, 1580, 261, 6332, 6553, 9133, 3159, 3972, 1984, 474, 9283, 8503, 5033, 67, 8173, 1126, 2066, 665, 7914, 1679, 7513, 73135, 9787, 8167, 8087, 6536, 3984, 7828, 8535, 34570, 5903, 7002, 9964, 8782, 1649, 38296, 4134, 9599, 5023, 14289, 20111, 71290, 4679, 9979, 8525, 6474, 2355, 3479, 30849, 29834, 9222, 3656, 9039, 6503, 5828, 2018, 6960, 3399, 6019, 45587, 3233, 1279, 7060, 6480, 3603, 35014, 4076, 8999, 4937, 6212, 9868, 1690, 4733, 396, 1541, 4533, 2514, 219, 520, 9524, 2419, 8249, 99773, 7658, 89162, 1916, 1814, 2128, 1209, 86138, 9133, 4779, 2996, 7893, 88272, 6463, 1916, 9985, 112, 6343, 7088, 7914, 9832, 5556, 6707, 3663, 6852, 5700, 2621, 1100, 8960, 14767, 6525, 18, 6116, 5819, 8432, 5338, 2855, 4989, 8967, 3502, 25468, 6143, 7360, 2485, 7214, 7641, 1345, 8547, 5021, 9176, 3726, 6420, 7456, 479, 7208, 6000, 4047, 6271, 74765, 2183, 6497, 1240, 5987, 3139, 3174, 4510, 2217, 4888, 5579, 4275, 9646, 857, 870, 7536, 4679, 7183, 1645, 2887, 6968, 704, 2082, 5040, 319, 6509, 1439, 8207, 38377, 9901, 9646, 274372, 2275, 1227, 4297, 7018, 6984, 29866, 8838, 260, 6018, 952, 9944, 1076, 550, 5238, 2695, 4344, 309848, 7030, 9028, 6573, 6929, 72995, 5979, 7255, 276, 68378, 6502, 1745, 1764, 14383, 3359, 4602, 918, 2736, 5259, 6613, 119, 5370, 8331, 6889, 1198, 869, 4589, 3630, 959, 7012, 7332, 2026, 8980, 1216, 5088, 3656, 157, 577, 9237, 5370, 1986, 14289, 266, 6820, 2224, 5893, 2153, 813, 9559, 665, 6807, 7917, 3867, 8937, 8, 2411, 9909, 841, 74765, 481, 667, 7072, 66271, 9978, 8366, 1325, 7271, 6686, 1752, 1376, 2114, 35014, 389276, 5212, 9356, 3792, 1532, 4148, 4663, 7411, 121, 6573, 5518, 3736, 3521, 6124, 48517, 7203, 9021, 22387, 7237, 4823, 2292, 1065, 600457, 526, 694, 5036, 5819, 2309, 19247, 2889, 3847, 1205, 5513, 4242, 7607, 4777, 9823, 5158, 9664, 5516, 4249, 3059, 4692, 4050, 477, 6014, 7080, 2506, 7567, 8548, 6112, 961, 402531, 9277, 670, 3326, 2791, 6998, 6053, 1113, 5120, 5378, 6680, 6232, 471, 7211, 6337, 6378, 16541, 3738, 7482, 1511, 9361, 7366, 3206, 3685, 1666, 51118, 21762, 2581, 7417, 6553, 5322, 4072, 4680, 1230, 3750, 9597, 9540, 43602, 1394, 9880, 5161, 3485, 5944, 1804, 7417, 2205, 4199, 2554, 9656, 95, 5203, 3310, 1124, 9921, 8708, 5235, 7628, 7499, 1612, 8333, 819, 6902, 180, 7435, 8847, 6424, 3316, 7810, 6676, 1111, 7237, 3473, 8159, 5872, 5708, 1987, 25, 4288, 2610, 39557, 6220, 8089, 4556, 3806, 6613, 9843, 99129, 1999, 543753, 7896, 575937, 9298, 9437, 636, 5387, 8751, 8207, 2460, 7620, 87527, 8480, 3393, 28550, 3169, 1788, 3060, 25200, 8793, 8200, 3816, 2944, 8808, 88, 5749, 5158, 1279, 1995, 962294, 2909, 8869, 84899, 6653, 624, 4148, 6332, 5199, 3814, 213, 6130, 7958, 21299, 9410, 430, 4951, 624, 5083, 189, 7863, 5149, 45632, 4973, 8379, 121, 2519, 8460, 7435, 3713, 4887, 7277, 6707, 7219, 2254, 1362, 5629, 3923, 5833, 3233, 1649, 4036, 2211, 1236, 1097, 7515, 1634, 5687, 3052, 9742, 897, 8926, 1159, 3469, 9935, 88272, 4386, 2233, 821, 550, 8869, 2889, 6879, 17305, 2404, 4330]

def solve(A):
    m = 1_000_000_007  # Modulus 10**9 + 7.
    def transform(A):
        B = []
        for k in range(len(A)):
            for i in range(len(A) - k):
                j = i + k + 1
                B.append(max(A[i:j]))
        return B
    return sum(transform(transform(A))) % m

A = [3, 2, 1]
>>> solve(A)
58

# S(A) => [3, 2, 1, 3, 2, 3]
# S(S(A)) => [3, 2, 1, 3, 2, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
# sum(S(S(A)) => 58

Improved solution, but still not good enough

Noting that only the sum of second transform needs to be returned rather than the array itself, the second call sums the values rather than appends them to B.

Furthermore, in the square matrix below the first row is simply A itself. Each subsequent row is the max of the item directly above and the item directly above and one left. For example, the lower right value of 3 (k=2, j=3) is calculated as max((k=1, j=2), (k=1, j=3)) = max(3, 2) = 3.

A = [3, 2, 1]

k  i  j  slice(i:j)  max(A[i:j])
-  -  -  ----------  -----------
0  0  1      0:1          3
0  1  2      1:2          2
0  2  3      2:3          1
1  0  2      0:2          3
1  1  3      1:3          2
2  0  3      0:3          3

  max(A[k:j])
       j
k   1  2  3  
- -----------
0 | 3  2  1  |
1 |    3  2  |
2 |       3  |
  ------------

Although this code is significantly faster than the naive code for A with more numbers, it still times out on all of the tests. There must be an improved algorithm. How can I do better?

def solve(A):
    m = 1_000_000_007  # Modulus 10 ** 9 + 7.
    B = max_vals = A
    while len(max_vals) > 1:
        max_vals = list(map(max, zip(max_vals, max_vals[1:])))
        B.extend(max_vals)
    max_vals = B
    total = sum(max_vals) % m
    while len(max_vals) > 1:
        max_vals = list(map(max, zip(max_vals, max_vals[1:])))
        total += sum(max_vals) % m
    return total % m

A = [3, 2, 1]
>>> solve(A)
58

Problem Details

Let A be a zero-indexed array of integers. For 0 <= i <= j < length(A), let Ai...j denote the subarray of A from index i to index j, inclusive.

Let's define the max transform of A as the array obtained by the following procedure:

• Let B be a list, initially empty.
• For k from 0 to length(A) - 1):
  • For i from 0 to length(A) - k - 1
    • Let j = i + k
    • Append max(Ai...j) to the end of B
• Return B

The returned array is defined as the max transform of A. We denote it by S(A).

Complete the function solve that takes an integer array A as input.

Given an array A, find the sum of the elements of S(S(A)), i.e., the max transform of the max transform of A. Since the answer may be very large, only find it modulo 10^9 + 7.

Problem constraints

• 1 <= n <= 2 * 10^5
• 1 <= Ai <= 10^6 (note that duplicate values may occur)

Answer 1

With 1719 numbers in big_A, S(big_A) will have 1478340 numbers, and S(S(big_A)) will have over 1 trillion (1092745316970) numbers. Adding up that many numbers will take a significant amount of time.

Most of the numbers are the same. S(S([3,2,1])) has 21 numbers, and with a sum of 58, a lot of those numbers will be 3. If you can figure out how many numbers are 3’s, you could multiply instead of add, saving significant time.

Consider just the maximum value in the input to the transform. It immediately dominates the two values in the next row, and three in the next row, and so on until it reaches either edge of the output rows:

*** *** *** max *** *** *** *** *** ***
  *** *** max max *** *** *** *** ***
    *** max max max *** *** *** ***
      max max max max *** *** ***
        max max max max *** ***
          max max max max ***
            max max max max
              max max max
                max max
                  max

The sum of all of the values is (4*7) * max + sum(left_side) + sum(right_side). So, if you can find the maximum in the input, and the location of the maximum, you can divide the problem into a directly calculated chunk, and 2 sub-problems. Recursive divide & conquer, FTW.

Code left to student.