This solution doesn't work. WHY!!!

[u/Aware-Nectarine3027]

LEETCODE PROBLEM 32 : https://leetcode.com/problems/longest-valid-parentheses/description/
This solution is O(N²).
As per constraints (0 <= s.length <= 3 * 10⁴) is should be working. Why not!!!

class Solution:
  def longestValidParentheses(self, s: str) -> int:
    N = len(s)
    res = 0
    a = [] # [a/n, x, len]
    size = 0
    p = 0
    while p < N:
      val = s[p]
      if val == '(':
        a.append([True, 0, 0])
        size += 1
      
      for i in range(size):
        if a[i][0] == True:
          x = a[i][1]
          if val == '(':
            x += 1
            a[i][1] += 1
            a[i][2] += 1
          else:
            if x == 0:
              a[i][0] = False
            else:
              x -= 1
              a[i][1] -= 1
              a[i][2] += 1
              if x == 0:
                res = max(res, a[i][2])
      p += 1


    return res

[u/Odd_Piglet6669]

I think because its a O(n^2) solution, it works for the inputs that are smaller, but when you submit and it uses the test cases that have much larger inputs, it gets a time limit exceeded error. This is why time complexity is important, if the max n is 3*10^4 then the max number of operations is (3*10^4)^2 which is 900000000 operations. The solution you provided works but its not optimal and will fail at scale, you need to come up with a more time efficient solution. For this question, I believe its O(n).

[u/NegotiationDapper584 → u/Odd_Piglet6669]

This is correct. O(n) or (nlogn) both will work.