Largest Multiple of Three LeetCode solution in Java

1
class Solution {
2
  public String largestMultipleOfThree(int[] digits) {
3
    int n = digits.length;
4
    Arrays.sort(digits);
5

6
    if (digits[digits.length - 1] == 0) {
7
      return "0";
8
    }
9

10
    int sum = 0;
11

12
    for (int i = 0; i < digits.length; i++) {
13
      sum += digits[i];
14
    }
15

16
    if (sum % 3 == 0) {
17
      StringBuilder sb = new StringBuilder("");
18

19
      for (int i = n - 1; i >= 0; i--) {
20
        sb.append(digits[i]);
21
      }
22

23
      return sb.toString();
24
    } else if (sum % 3 == 1) {
25
      int modOne = -1;
26

27
      for (int i = 0; i < n; i++) {
28
        if (digits[i] % 3 == 1) {
29
          modOne = i;
30
          break;
31
        }
32
      }
33

34
      if (modOne == -1) {
35
        int[] idx = new int[2];
36
        Arrays.fill(idx, -1);
37

38
        for (int i = 0; i < n; i++) {
39
          if (digits[i] % 3 == 2) {
40
            if (idx[0] == -1) {
41
              idx[0] = i;
42
            } else {
43
              idx[1] = i;
44
              break;
45
            }
46
          }
47
        }
48

49
        if (idx[1] == -1) {
50
          return "";
51
        } else {
52
          digits[idx[0]] = -1;
53
          digits[idx[1]] = -1;
54
        }
55
      } else {
56
        digits[modOne] = -1;
57
      }
58
    } else {
59
      int modTwo = -1;
60

61
      for (int i = 0; i < n; i++) {
62
        if (digits[i] % 3 == 2) {
63
          modTwo = i;
64
          break;
65
        }
66
      }
67

68
      if (modTwo == -1) {
69
        int[] idx = new int[2];
70
        Arrays.fill(idx, -1);
71

72
        for (int i = 0; i < n; i++) {
73
          if (digits[i] % 3 == 1) {
74
            if (idx[0] == -1) {
75
              idx[0] = i;
76
            } else {
77
              idx[1] = i;
78
              break;
79
            }
80
          }
81
        }
82

83
        if (idx[1] == -1) {
84
          return "";
85
        } else {
86
          digits[idx[0]] = -1;
87
          digits[idx[1]] = -1;
88
        }
89
      } else {
90
        digits[modTwo] = -1;
91
      }
92
    }
93

94
    StringBuilder sb = new StringBuilder("");
95

96
    for (int i = n - 1; i >= 0; i--) {
97
      if (digits[i] != -1) {
98
        sb.append(digits[i]);
99
      }
100
    }
101

102
    if (sb.length() > 0 && sb.toString().charAt(0) == '0') {
103
      return "0";
104
    }
105
    return sb.toString();
106
  }
107
}